Search a 2D Matrix

01/13/2018 update
--------------------------------------------------------------------------------------------------------------------------
Why is high set to m*n  - 1 instead of m*n? If we set high to m*n, with [[1]]. mid would be
01/12/2018 update
Refined template solution:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0|| matrix == null|| matrix[0].length == 0) return false;
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low < high) {  
            int mid = low + (high - low)/2; 
            int midValue = matrix[mid/n][mid%n];
            if (target == midValue) {  
                return true;  
            } else if (target > midValue){  
                low = mid + 1;  
            }  else {
                high = mid;
            }
        }

        return matrix[low/n][low%n] == target;
    }
}

Initializing hi value must be very careful. In this case, if we set hi to m*n, array would be out of boundary.

For example, [[1]], hi = 1, lo = 0. mid % n = 1. It's out of boundary.
--------------------------------------------------------------------------------------------------------------------------
01/11/2018 update
No need to search twice, treat 2D matrix as one array. The mid value can be retrieved by matrix[mid/col][mid%col].

This problem can not follow template, cuz double check is not obvious. But double check must be performed if use the template.

Solution:

class Solution {
    public boolean searchMatrix(int[][] matrix, 
                                int target) {
        if (matrix.length == 0|| 
            matrix == null|| 
            matrix[0].length == 0) return false;
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low + 1 < high) {  
            int mid = low + (high - low)/2; 
            int midValue = matrix[mid/n][mid%n];
            if (target == midValue) {  
                return true;  
            } else if (target > midValue){  
                low = mid;  
            }  else {
                high = mid;
            }
        }
        
        if (matrix[high/n][high%n] == target) return true;
        if (matrix[low/n][low%n] == target) return true;
        return false;
    }
}

--------------------------------------------------------------------------------------------------------------------
思路：
2次搜索，第一次先找row，可以只看每一行的第一个元素和target比较大小。第二次找row在row里面搜索。