分析

• 本题的考点：二分。

• 二维数组按照从上向下依次一行一行展开后是递增的，因此可以使用二分。

• 我们二分的区间为$[0, n \times m - 1]$，n、m为行数、列数。关键问题对于区间中的mid，如何转为二维坐标？答案是：(mid / m, mid % m)。

代码

• C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {

        int n = matrix.size(), m = matrix[0].size();
        if (matrix[0][0] > target || matrix[n - 1][m - 1] < target) return false;

        int l = 0, r = n * m - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }
        return matrix[l / m][l % m] == target;
    }
};

• Java

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        int n = matrix.length, m = matrix[0].length;

        int l = 0, r = n * m - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }
        return matrix[r / m][r % m] == target;
    }
}

时空复杂度分析

• 时间复杂度：$O(log(n \times m))$，n、m为行数、列数。

• 空间复杂度：$O(1)$。