如何在二维矩阵中用二分查找一个目标值？两类矩阵有什么不同？

简化版

要区分两类矩阵:① 每行升序、且每行第一个 > 上一行最后一个(整体展平就是一个有序数组)——把二维下标映射成一维,直接二分,O(log(m·n));② 每行升序、每列也升序(但行列之间无强约束)——不能整体二分,用「从右上角(或左下角)开始走」的方法,每步排除一行或一列,O(m+n)。选哪种取决于矩阵的有序性质。

详细版

类型一:整体有序矩阵(LeetCode 74)

每行升序 + 每行首元素 > 上一行尾元素 → 把矩阵看成一个长度 m*n 的有序数组,一维下标 k 对应 matrix[k / cols][k % cols]:

boolean searchMatrix(int[][] mat, int target) {
    int m = mat.length, n = mat[0].length;
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = mat[mid / n][mid % n];   // 一维下标映射回二维
        if (val == target) return true;
        else if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

O(log(m·n))。

类型二:行列都有序矩阵(LeetCode 240)

每行升序、每列升序,但不保证「行首 > 上行尾」。从右上角开始:

boolean searchMatrix2(int[][] mat, int target) {
    int r = 0, c = mat[0].length - 1;     // 右上角
    while (r < mat.length && c >= 0) {
        if (mat[r][c] == target) return true;
        else if (mat[r][c] > target) c--;  // 当前太大 → 排除这一列
        else r++;                           // 当前太小 → 排除这一行
    }
    return false;
}

O(m + n)。

完整版教学

一、先分清是哪类矩阵(关键)

二维矩阵搜索最容易错的地方是没分清矩阵的有序性质就套模板。有两类完全不同的矩阵:

类型一(整体有序):每行从左到右升序,且下一行的第一个元素比上一行的最后一个元素还大。这意味着把所有行首尾相接展平,就是一个完整的升序数组。可以整体二分。
类型二(行列有序):每行升序、每列升序,但行与行之间没有「行首 > 上行尾」的强约束(比如第二行第一个可能比第一行第三个小)。展平后不是有序的,不能整体二分。

面试时先问清/看清是哪类,再选方法。用错方法会得到错误结果。

二、类型一:降维成一维二分

类型一因为「展平即有序」,可以把二维矩阵虚拟地看成一维有序数组,直接对下标 [0, m*n-1] 二分。唯一的技巧是一维下标 k 和二维下标的互相转换:

行号 = k / n(n 是列数),列号 = k % n。

这样每次取中点 mid,用 mat[mid/n][mid%n] 取值比较即可,其余和普通二分一模一样。时间 O(log(m·n)),是最优的。

三、类型二:从角落开始的「排除法」

类型二不能整体二分,但有个巧妙的 O(m+n) 方法:从右上角(或左下角)开始走。以右上角为例(它是所在行的最大值、所在列的最小值):

mat[r][c] == target:找到。
mat[r][c] > target:当前值太大。因为它是这一列里最小的(列升序,它在列顶),所以这一整列都比 target 大,排除整列,c--(左移)。
mat[r][c] < target:当前值太小。因为它是这一行里最大的(行升序,它在行尾),所以这一整行都比 target 小,排除整行,r++(下移)。

每一步排除一行或一列,最多走 m + n 步,所以 O(m + n)。

四、为什么从「右上角」而不是「左上角」

选角落有讲究:必须选一个「往两个方向走能分别变大和变小」的角。

右上角:往左(c—)变小、往下(r++)变大——两个方向单调相反,能据比较结果明确排除行或列。可用。
左下角:往上变小、往右变大——同样两个方向相反,也可用。
左上角 / 右下角:两个方向都变大(或都变小),无法根据比较结果排除——不能用。

所以记住:从右上角或左下角开始,利用「一个方向增、一个方向减」的性质做排除。

五、两类方法的对比

	类型一(整体有序)	类型二(行列有序)
矩阵性质	展平后完全有序	行升序 + 列升序
方法	降维成一维二分	从右上/左下角排除
时间	O(log(m·n))	O(m + n)

类型一更强的有序性换来了更快的 O(log) 查找;类型二有序性弱,只能 O(m+n)。别把类型一的一维二分用到类型二上(会错),也别把类型二的 O(m+n) 用到类型一(能更快)。

六、复杂度与要点

类型一:O(log(m·n)),核心是下标映射 mat[k/n][k%n]。
类型二:O(m+n),核心是从右上/左下角、每步排除一行或一列。
要点:先判断矩阵属于哪一类,再选对应方法。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：必须先区分“整矩阵可展平有序”和“仅行列分别有序”两种前提。

对应的状态推进是：前者把 k 映射为 row=k/cols、col=k%cols；后者从右上角逐行或逐列排除。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。展平二分 O(log(mn))；右上角排除 O(m+n)。

带数字走一遍：3×4 矩阵的一维下标 7 映射到 (1,3)。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	矩阵不能为空且各行长度通常应一致；具体方法取决于有序定义
时间复杂度	O(log(mn)) 或 O(m+n)
额外空间	O(1)
关键边界	m×n 乘法和下标计算需防溢出；左上角不能唯一决定移动方向
替代方案	只按行有序且行间无关系时可逐行二分

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“矩阵不能为空且各行长度通常应一致；具体方法取决于有序定义”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(log(mn)) 或 O(m+n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“展平二分 O(log(mn))；右上角排除 O(m+n)”。
误区：重复值和边界值不会改变代码。 m×n 乘法和下标计算需防溢出；左上角不能唯一决定移动方向。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“必须先区分“整矩阵可展平有序”和“仅行列分别有序”两种前提”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“3×4 矩阵的一维下标 7 映射到 (1,3)”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“只按行有序且行间无关系时可逐行二分”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

二维矩阵搜索先分类:类型一(每行升序 + 行首>上行尾,展平即有序)→ 映射一维下标 mat[k/n][k%n] 直接二分,O(log(m·n));类型二(行升序+列升序,展平无序)→ 从右上角(或左下角) 开始,大了排除整列(c—)、小了排除整行(r++),O(m+n)。选右上/左下是因为其「一方向增、一方向减」才能排除;左上/右下不行。别把两类方法用混。

简化版

详细版