【二分】搜索二维矩阵 Ⅱ

240. 搜索二维矩阵 II

矩阵中的元素具有以下特性：

• 每行元素从左到右按升序排列；
• 每列元素从上到下按升序排列。

那我们如何利用这样的有序性高效查找 target 呢？

为了利用矩阵的有序性缩小搜索范围，我们希望每次比较当前元素与 target 后，都能排除一部分不可能包含目标值的区域。

观察矩阵的四个角，可以发现，左上角的元素是整个矩阵的最小值，右下角的元素是整个矩阵的最大值。

结合矩阵的行、列有序性，我们可以进一步观察右上角和左下角这两个位置。以右上角为例，可以发现，该位置的元素是所在行的最大值，同时也是所在列的最小值。

我们记右上角元素为 cur：

• 当 cur < target 时，由于 cur 是所在行的最大值，该行所有元素都小于 target，因此可以排除当前行。
• 当 cur > target 时，由于 cur 是所在列的最小值，该列所有元素都大于 target，因此可以排除当前列。
• 当 cur == target 时，说明找到了目标值，直接返回 true。

因此，从右上角开始搜索，就可以根据每次比较的结果，不断缩小搜索范围。排除一行或一列后，剩余区域仍然保持每行、每列有序的性质，因此可以继续按照上述方法搜索。

同理，左下角也具有类似的性质，因此也可以作为搜索起点。这里选择右上角进行说明。

我们从右上角出发，并使用变量 top 和 right 分别维护当前搜索区域的上边界和右边界。

每次比较后，根据上述规则移动对应边界，逐步缩小搜索范围。当搜索区域为空时，说明 target 不在矩阵中，返回 false。

基于这一思路，可写出如下代码：

▼
java
复制代码
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int top = 0, right = n - 1;
    while (top < m && right >= 0) {
        int cur = matrix[top][right];
        if (cur == target) {
            return true;
        } else if (cur > target) {
            right--;
        } else {
            top++;
        }
    }
    return false;
}

复杂度分析:

• 时间复杂度：$O(m+n)$。每次循环都会排除一整行或一整列，top 最多增加 $m$ 次，right 最多减小 $n$ 次。
• 空间复杂度：$O(1)$。只使用了常数个额外变量。