前几天我把力扣热题100Hot100里二分相关的题集中过了一遍做到“搜索二维矩阵”时反而花了最多时间复盘。题目本身一句话就能说清楚给你一个 m x n 矩阵每一行从左到右递增而且每一行的第一个数一定大于上一行的最后一个数给定 target判断它在不在矩阵里。看起来简单但真正难点在于你能不能把这个二维结构看成一条已经排好序的一维链然后干净利落地写出二分。这篇就把我拆过的两种解法、边界条件、常见翻车点以及从它延伸出去的变种题按实际做题的顺序完整讲一遍。1. 矩阵的“全序”条件所有解法成立的前提1.1 这个矩阵特殊在哪儿普通二维矩阵哪怕每一行递增、每一列递增行与行之间也不一定有确定的先后关系。但本题多了一个关键约束“每一行的第一个整数大于前一行的最后一个整数”这句话直接宣告了整个矩阵按行展开以后是一个严格递增的一维数组。举个例子[[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]把它一行一行接起来得到序列1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60。这确实是一条严格递增的序列。也就是说目标值在矩阵里的位置其实就等价于在一个有序数组中的位置。我当时第一次看这道题第一反应是“先二分行再二分列”并没有先停下来想这个问题。后来刷多了才意识到这个“全序”视角才是整道题的根一旦你意识到它可以拉直成一维后面所有解法的复杂度上界都清楚了。1.2 有序性决定算法上界面试的时候如果面试官问“这题为什么可以二分”最忌讳的回答是“因为题目说了每行有序”。真正的关键点是整个矩阵按行展开后仍然有序这是一个全局性质而不只是局部性质。正因为有这个全局性质搜索区间可以稳定地每次缩小一半时间复杂度能做到 O(log(m*n))空间 O(1)。反过来如果题目只保证“每行内部有序”但行与行之间没有大小关系那你只能退化成对每一行做二分复杂度是 O(m log n)如果题目只保证“每行递增且每列递增”但不保证全序那就是另一道经典题后面第 5 节会展开最优也只能做到 O(mn)。所以面试时看到这种题先别急着写代码先把题目的条件翻译成一句“整个矩阵展开是一个有序数组”这就已经赢了一半。很多时候面试官考察的并不是你能不能写对二分而是你有没有意识到这个全局有序性决定了算法能达到什么级别。1.3 重复值会影响二分的写法吗这是一个常见的附加追问。题目默认值不重复但你可以自己推一下如果矩阵里有重复元素二分还成立吗其实成立。二分的根基是“搜索区间单调可判断”重复值只是让相等分支提前返回 ture或者让区间收缩的边界条件略复杂一点。只要坚持用while left right这种标准写法相等时返回大于时缩右边界小于时缩左边界重复值并不会导致逻辑错误。怕的反而是“找到任意一个相等的就直接返回”这种需求那对重复值无所谓如果你要找“第一个等于 target 的位置”那就需要你用 lower_bound 那套语义而不是标准查找。不过力扣这道题只要求判断在不在所以直接按标准二分写就行不用过度设计。2. 解法一先定位行再在行内二分2.1 把行首当成一个独立的有序数组既然整个矩阵展开后有序那么一个更直观的思路是先确定 target 可能在的“那一行”。因为矩阵满足“每一行的第一个数都比上一行所有数大”所以各行行首天然构成一个递增数组[1, 10, 23]我们可以先在这个递增数组里做一次二分目标是找到“最后一个行首小于等于 target 的行”。为什么是最后一个因为 target 如果存在它一定位于某一行中而这一行的首元素必须不大于 target同时下一行的首元素必须大于 target。只要满足这两个条件target 要么在这一行要么根本不存在。要注意这个“最后一个”很关键。比如 target 11行首数组 [1, 10, 23] 中10 和 23 都大于等于……不对10 11但 23 11所以满足“行首 target”的行是第 0 行和第 1 行而 target 真正可能存在的行是最后一个满足条件的行也就是第 1 行。2.2 二分退出后 left 和 right 分别代表什么这是最容易翻车的地方。很多人写二分只背模板循环一退出就开始迷糊到底用 left 还是 right我习惯用这个写法left, right 0, m - 1 while left right: mid (left right) // 2 if matrix[mid][0] target: left mid 1 else: right mid - 1循环结束后left指向第一个“行首大于 target”的行right指向最后一个“行首小于等于 target”的行。也就是说right才是我们需要的候选行。如果right 0说明 target 比第一行的行首还小直接返回 False。很多初学者在这里会用left因为平时背的模板都是“循环结束后 left 指向目标位置”。但那个结论只适用于查找“第一个满足条件的位置”。这里我们找的是“最后一个满足条件的位置”所以语义刚好反过来。解决的办法很简单别去死记硬背 left 还是 right手动推一遍。比如 target 11 时初始 left0, right2mid1matrix[1][0]1010 11所以 left2此时 left2, right2mid2matrix[2][0]2323 11所以 right1退出循环right1row1正确。推这一遍以后你对这块的判断就不容易再错了。2.3 完整代码from typing import List class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) # Step 1: 在行首数组中找最后一个 target 的行 left, right 0, m - 1 while left right: mid (left right) // 2 if matrix[mid][0] target: left mid 1 else: right mid - 1 row right if row 0: return False # Step 2: 在 row 行内做普通二分 left, right 0, n - 1 while left right: mid (left right) // 2 if matrix[row][mid] target: return True elif matrix[row][mid] target: left mid 1 else: right mid - 1 return False2.4 空矩阵和空行的防御我在实际刷题时第一遍写的版本经常不判断not matrix[0]结果遇到matrix [[]]这种用例直接报错。LeetCode 的隐藏用例里有很多这类边缘输入面试手写代码时也常常会被面试官用这一条“测试”你的工程意识。正确做法是进门先防御if not matrix or not matrix[0]: return False这两句话必须放在取m,n之前。因为一旦matrix为空你没法访问matrix[0]一旦matrix[0]为空虽然len(matrix)不为 0但列数 n0后面所有索引访问都会越界。这个细节虽然简单但我给不少人 review 代码时发现真的有人会因为漏掉not matrix[0]而在白板面试上卡壳。不要觉得这是小事工程意识的考察往往就在这种地方。3. 解法二把二维矩阵拉直成一个虚拟有序数组3.1 从全序条件到“一维化”解法一很直观但它需要两个二分循环。解法二则更进一步既然矩阵展开后就是一个递增数组那我可以直接把这个数组当成一个逻辑上的一维数组来做二分。但矩阵本身还是二维存储的所以需要一个“一维下标 - 二维坐标”的映射行号mid // n列号mid % n注意这里是对列数n取模不是对行数m。很多人在这个地方写反我用一个小例子验证一下假设 m3, n4一维下标 mid6。对应展开序列的第 6 个元素从 0 开始数。6 // 4 16 % 4 2对应矩阵第 1 行第 2 列即值为 16 的位置。我们验证展开序列索引 01, 13, 25, 37, 410, 511, 616完全对得上。这个映射的本质是一维下标先按每行元素个数n整除得到行号余数就是列号。很多教材说“二维数组映射为一维”时喜欢用i * n j这里我们只是把它反过来用。3.2 完整代码from typing import List class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid (left right) // 2 cur matrix[mid // n][mid % n] if cur target: return True elif cur target: left mid 1 else: right mid - 1 return False相比解法一它的代码更短也不需要考虑“行定位后row 0”这种特殊分支逻辑上更干净。唯一的门槛就是下标映射那两行只要理解了这题基本不可能写错。3.3 两种解法对比面试时怎么选对比维度解法一先定位行再行内二分解法二一维展开二分核心思想行首数组上二分行范围行内再二分利用全局有序性把矩阵当一维数组时间复杂度O(log m log n)O(log(m*n))空间复杂度O(1)O(1)代码量两段二分稍长一段二分更短容易出错left/right 语义搞反mid%n 与 mid%m 写混面试时先用哪个直观适合先讲思路简洁适合作为优化补充我个人的建议是面试时先讲解法一因为它的思路直观容易让面试官跟上你的节奏然后提一句“其实因为矩阵本身满足全局递增还可以直接把下标映射成一维数组做一次二分代码更简洁”顺手把解法二写出来。这样既展示了你的基础功底又展示了你在“有序性”上的敏感度。如果你是在刷题阶段看这篇我更推荐主练解法二。因为它省掉了行定位那一步的判断写起来快也不容易在边界条件上翻车特别适合面试高压状态下 5 分钟内写完的场景。4. 边界条件、测试用例与常见翻车点4.1 一组值得反复跑的最小用例刷题最怕的是“用例过了就以为过了”其实很多隐藏问题都藏在边界里。我每次写这类二分题都会拿下面这组用例快速过一遍输入预期覆盖点[]false空矩阵[[]]false空行[[1]], target1true单元素命中[[1]], target0false单元素未命中[[1,5,9]], target5true单行命中[[1],[5],[9]], target5true单列命中[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target3true第一行普通位置同上target7true第一行行尾同上target10true某行行首同上target8false落在两行元素之间同上target0false小于全局最小值同上target80false大于全局最大值尤其是“单行”和“单列”这两种形状最容易暴露m和n用混的问题。比如解法二里如果手滑把mid % n写成mid % m在 m3, n4 这种矩阵上就直接算错但如果 mn1或者 mn2你甚至可能侥幸跑过几个用例。所以刷题时一定要主动拿非方阵去测。4.2 我见过的三个高频翻车现场第一个翻车点matrix[0]为空时没有提前返回。这会导致n 0后面right m * 0 - 1 -1循环根本不进最后返回 false看起来结果可能对但一旦 matrix 本身也为空就是真正的异常访问了。所以空矩阵和空行必须分开判断。第二个翻车点解法一的row用了left而不是right。我见过不止一个人写完行定位后直接拿left去行内二分。如果 target 小于所有行首left会停在 0这时候到第 0 行里二分大概率返回 false结果碰巧对但 target 落在第 0 行中间时left可能已经右移到 1就会漏掉正确答案。这就是典型的“样例没过”或者“样例过了但思路错了”。第三个翻车点一维映射时把mid // n和mid % n搞反或者混用尤其是在“n 很小、m 很大”的矩阵上。我总是提醒自己行号 下标 / 列数而不是下标 / 行数。你可以理解为展开时先数完一整行才换行所以“跨行”的除法是列数 n。4.3 边界思考的“心里演练”除了跑用例我还有一个习惯写完二分后在脑子里对“target 比最小值还小”“target 比最大值还大”“target 恰好等于某行行首”这三种情况各推演一遍。推演的价值在于它能逼你把循环退出的瞬间看清楚。以解法二为例target 小于所有元素二分不断缩右边最后 left0, right-1循环退出返回 false。此时没有任何越界风险。target 大于所有元素二分不断缩左边最后 leftmn, rightmn-1退出返回 false。这里也不会访问matrix[left // n]因为循环已经结束了。target 恰好等于 matrix[0][0]第一次 mid 不一定是 0但无论怎么二分最终一定会遇到 cur target 并返回 true逻辑成立。做完这三步推演基本可以确认你的代码没有越界问题也验证了返回值语义是否正确。5. 从全序到部分序240 题到底改了什么5.1 去掉“行首大于上一行行尾”一次二分就失效很多人在力扣刷到这道题之后还会遇到它的姊妹题“搜索二维矩阵 II”题号 240。两道题长得特别像都是二维矩阵搜索但条件有一个关键区别240 题只保证每一行从左到右递增每一列从上到下递增不保证整个矩阵按行展开后有序。举个最直接的反例[[1, 3], [2, 4]]这个矩阵每行递增、每列递增但展开成一维是 1, 3, 2, 4并不是有序的。target2 时如果你用一次二分mid(03)//21对应元素 3因为 3 2你会把右半部分舍弃搜索区间变成 [0,0]于是错误地返回 false——但 2 明明在矩阵里。所以在 240 题里解法二的“一维化二分”完全不可用。你必须在“行 / 列分别有序”的局部性质上重新设计搜索路径。5.2 Z 字形搜索为什么是 O(mn)从右上角出发是一个经典做法。设当前坐标为 (row, col)初始 row0, coln-1如果 matrix[row][col] target直接返回 true如果 matrix[row][col] target说明当前这一列下方所有元素都大于当前值一定大于 target所以整列都可以排除col 左移如果 matrix[row][col] target说明当前这一行左侧所有元素都小于当前值一定小于 target所以整行都可以排除row 下移。因为每次操作都能排除一整行或一整列所以最坏情况下走 mn 步就到边界复杂度是 O(mn)。Z 字搜索之所以从右上角开始而不是左上角是因为左上角是矩阵最小值的位置往右往下都比它大你没法决定往哪个方向走右下角同理。右上角是一个天然的“分界点”左边都比它小下边都比它大刚好能根据 target 与当前值的大小决定唯一的移动方向。5.3 这道题在 Hot100 二分题单里的位置如果你是按专题刷 Hot100可以顺手把这几道题放在一起对比搜索二维矩阵本题全局有序一维二分即可搜索二维矩阵 II240 题行列分别有序Z 字搜索 O(mn)搜索旋转排序数组局部有序需要先判断哪一半有序再二分在排序数组中查找元素的第一个和最后一个位置二分的边界语义lower_bound / upper_bound寻找峰值不是直接找 target而是根据相邻关系判断上升 / 下降趋势。这些题本质都是在问同一个问题搜索区间是否单调每一步能稳定排除掉哪一片。你会发现二分模板本身并不难难的是“是否具备二分条件”以及“区间收缩后 target 位于哪一半”这两个判断。把“搜索二维矩阵”吃透尤其是理解“全序展开”这个视角后面做旋转数组、找峰值很多思路都能复用。我个人现在刷 Hot100 二分专题的习惯是每道题先花 30 秒在纸上画一下结构和搜索顺序再动手写循环。尤其是这类“二维嵌套有序”的题花在判断单调性上的时间永远比写代码的时间更值钱。这道题我至少给不同的人讲过三遍每次讲到最后都会发现真正让别人卡住的不是二分本身而是没有意识到“矩阵拉直后就是一个数组”这个隐藏条件。希望这篇复盘也能帮你把这一层窗户纸捅破。