74. 搜索二维矩阵

74. 搜索二维矩阵 - 力扣（LeetCode）

思路：

方法1：可以使用两次二分，先在第一列上二分，然后确定第一个小于等于target的行r，然后再在r行上二分，找到第一个小于等于target的值t。如果r不存在或者t不存在，返回false，否则返回true。 

方法2：把二维数组通过坐标变换转为一维数组，使用一次二分就行了。

总结：

二分的应用。

代码：

 方法1：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        int m0 = 0;
        int n0 = 0;
        while(m0 <= m) {
            int mid = m0 + (m - m0)/2;
            if(matrix[mid][0] > target) {
                m = mid - 1;
            }
            else {
                m0 = m0 + 1;
            }
        }
        if(m < 0) return false;
        while(n0 <= n) {
            int mid = n0 + (n - n0)/2;
            if(matrix[m][mid] > target) {
                n = mid - 1;
            }
            else {
                n0 = n0 + 1;
            }
        }
        return n >= 0 && matrix[m][n] == target ? true : false;
    }
 
}

方法2：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0, r = m*n - 1;
        while(l <= r) {
            int mid = l + (r - l)/2;
            if(matrix[mid/n][mid%n] < target) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return l < m * n && matrix[l/n][l%n] == target ? true : false;
    }
 
}