解法一：两次二分

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int x = binarySearch1(matrix, target);
        int y = binarySearch2(matrix[x], target);
        return matrix[x][y] == target;
    }

    private int binarySearch2(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    private int binarySearch1(int[][] matrix, int target) {
        int l = 0, r = matrix.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (matrix[mid][0] <= target) l = mid;
            else r = mid - 1;
        }
        return l;
    }
}

复杂度分析：

• 时间复杂度：O(logn + logm)
• 空间复杂度：O(1)

解法二：二维矩阵转一维，一次二分

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length, col = matrix[0].length;
        int l = 0, r = row * col - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (matrix[mid / col][mid % col] <= target) l = mid;
            else r = mid - 1;
        }
        return matrix[l / col][l % col] == target;
    }
}

复杂度分析：

• 时间复杂度：O(log(n*m))
• 空间复杂度：O(1)