搜索二维矩阵 II 图解题解

这道题真正在问什么

给一个 m 行 n 列的矩阵，每行从左到右升序、每列从上到下升序，判断 target 是否在其中。要小心它和「搜索二维矩阵 I」的区别：这里只有行、列各自有序，整体并不能摊平成一个有序的一维数组——上一行的末尾未必小于下一行的开头，所以把整个矩阵当一维序列做一次全局二分是行不通的。

暴力和逐行二分分别卡在哪

逐格扫描要 O(m×n)，完全没用上有序性。稍好的做法是对每一行做二分查找，O(m·log n)——它用了行有序，却把列有序整个浪费了。两个维度的有序信息都在手上，理想的算法应该做到「一次比较就排除一大片」。于是问题变成：站在哪个位置比较，才能让「比 target 大」和「比 target 小」各自指向一个确定无疑的排除方向？

为什么偏偏要从右上角出发

右上角的元素有个独一无二的身份：它是所在行的最大值，同时是所在列的最小值。拿它和 target 比，两种结果都有干脆的结论——它比 target 大，说明它下方整列只会更大，这一列可以整列扔掉，指针左移；它比 target 小，说明连本行最大的都不够，这一行整行扔掉，指针下移。相比之下，左上角是行列双最小、右下角是行列双最大，比较结果无论偏大偏小都无法唯一确定该往哪走，一格都排除不了。左下角与右上角对称（本列最大、本行最小），同样可行。

每一步的排除为什么都不冤枉

这个走法可以看成拿单调性做贪心排除：每次比较后被扔掉的那一行或一列，有升序性质背书，绝不可能藏着 target；而 target 若存在，必然还留在剩余的子矩阵里——循环全程保持「候选区域始终包含答案（若答案存在）」这个不变量。指针只会向左或向下、永不回头，所以既不漏查也不绕圈，直到命中返回 true，或走出矩阵边界宣告不存在。

复杂度怎么数，边界在哪里

每一步要么列指针减一、要么行指针加一：列最多减 n 次、行最多加 m 次，总步数不超过 m+n，时间 O(m+n)，空间 O(1)，只用两个指针。实现上的两个坑：循环条件必须在指针越界（列减到负数、行加到 m）时停下并返回 false；比较后的移动方向别写反——比 target 大是左移砍列、比 target 小才是下移砍行，写反会把可能藏着答案的区域整片扔掉。

Python

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    r, c = 0, len(matrix[0]) - 1   # 从右上角出发
    while r < len(matrix) and c >= 0:
        v = matrix[r][c]
        if v == target:
            return True
        elif v > target:
            c -= 1                  # 太大，砍掉这一列
        else:
            r += 1                  # 太小，砍掉这一行
    return False

C++

bool searchMatrix(vector<vector<int>>& m, int target){
    if (m.empty() || m[0].empty()) return false;
    int r = 0, c = m[0].size() - 1;     // 右上角
    while (r < (int)m.size() && c >= 0) {
        int v = m[r][c];
        if (v == target) return true;
        else if (v > target) c--;       // 砍列
        else r++;                       // 砍行
    }
    return false;
}

Java

public boolean searchMatrix(int[][] m, int target) {
    if (m.length == 0 || m[0].length == 0) return false;
    int r = 0, c = m[0].length - 1;     // 右上角
    while (r < m.length && c >= 0) {
        int v = m[r][c];
        if (v == target) return true;
        else if (v > target) c--;       // 砍列
        else r++;                       // 砍行
    }
    return false;
}