刷 LeetCode 的都知道第 74 题“搜索二维矩阵”属于那种看起来简单、一写就错、面试还特别爱考的题目。它表面上是个矩阵查找问题本质上考的是二分法能不能从一维数组平滑迁移到二维结构。这篇文章我会把四种主流解法全部拆开讲清楚包括暴力遍历、右上角线性搜索、两次二分和一次二分把矩阵当一维数组处理每一种的思路、代码、边界条件和复杂度全给你对齐。除此之外我还会专门复盘我实际刷题和面试中踩过的坑比如空矩阵怎么处理、mid 映射到行列时下标为什么总算错、二分循环条件怎么写才不会死循环。无论你是刚开始刷题的新手还是准备面试想快速过一遍高频题这篇内容都能直接拿去用。1. 先读懂题目它到底在考你什么1.1 题目描述与示例还原LeetCode 74 题“搜索二维矩阵”的原题是这样的给你一个 m x n 的矩阵 matrix 和一个目标值 target矩阵满足两个特性每一行的所有元素从左到右递增每一行的第一个元素大于上一行的最后一个元素。你要在这个矩阵里判断 target 是否存在存在返回 true不存在返回 false。举个例子一个 3 x 4 的矩阵[1, 3, 5, 7] [10, 11, 16, 20] [23, 30, 34, 60]如果 target 是 3返回 true如果 target 是 13返回 false。题目本身不长约束条件也简单但它把“有序结构上的查找”这件事换了个壳不是给你一个排好序的一维数组而是给你一个排好序的二维矩阵。很多第一次做这题的人会犯迷糊矩阵是两个维度二分法怎么套1.2 隐藏条件才是解题关键这道题能高效解决完全取决于题目开头给的那两个特性。第一每一行内部递增第二行与行之间也是接续递增的。这两个条件合在一起意味着整个矩阵如果把每一行首尾相接可以展开成一个严格递增的一维数组。我见过很多人忽略这个结论直接去套 LeetCode 240 题“搜索二维矩阵 II”的解法那道题每行递增、每列递增但行首和上一行行尾没有大小关系。74 题比 240 题多了一个“全局有序”的条件所以 74 题有更强的解法比如一次二分而 240 题做不到只能用线性搜索。你只要抓住了“矩阵可以展开成一维有序数组”这一点这题的主干思路就已经通了。剩下的问题就变成了如何把一个一维下标映射回二维的行列坐标以及二分法的边界到底怎么卡。2. 解法一暴力遍历为什么说它“能用但没用”2.1 暴力解法的思路与复杂度最直白的想法就是双重循环把整个矩阵扫一遍。如果 matrix[i][j] 等于 target 就返回 true扫完都没找到就返回 false。时间复杂度是 O(m * n)空间复杂度是 O(1)。一个简单的实现长这样class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False for row in matrix: for num in row: if num target: return True return False代码没问题逻辑也没问题但这道题出现在面试里如果你只给出暴力解法基本等于在告诉面试官“我没有分析题目数据结构的特殊性”。2.2 暴力解法在面试中怎么用我不建议直接跳过暴力解不提但更不建议只给暴力解。面试里比较聪明的做法是先秒答暴力解紧接着说一句“但是矩阵是有序的我们可以用更好的方法把复杂度降到对数级别”。这样既展示了你能快速写出正确代码也展示了你有优化意识。暴力解法真正的意义有两个第一它是最不容易出错的基准实现当你后面的二分版本写崩了至少还有一个保底答案第二它帮助你验证题目理解是否正确尤其是各种边界示例跑暴力解可以快速确认自己有没有读错题。不过在实际刷题和面试场景里暴力解只能当跳板不能当终点。下面几种解法才是真正的重点。3. 解法二从右上角出发的线性搜索一个妙招通吃两个题3.1 为什么从右上角开始而不是左上角很多第一次接触这道题的人会困惑既然矩阵有序为什么不从左上角开始搜我们可以推演一下假设从左上角开始当前位置是 1target 是 16我们发现 1 比 16 小那么下一步应该往右还是往下这个问题无解因为右边和下边的数都比当前大你无法排除任何一个方向。但如果从右上角开始情况完全不同。右上角的数有一个特性它左边的数都比它小它下边的数都比它大。于是我们可以做一个类似“折半查找”的决策如果 target 等于当前位置直接返回 true如果 target 小于当前位置说明当前列可以整体排除向左移动一列如果 target 大于当前位置说明当前行可以整体排除向下移动一行。这个技巧有个更形象的叫法Z 字形搜索因为你每次移动都是向左或向下路径像英文字母 Z。3.2 代码实现与复杂度分析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]) row, col 0, n - 1 while row m and col 0: current matrix[row][col] if current target: return True elif current target: col - 1 else: row 1 return False每次要么左移一列要么下移一行最多走 m n 步所以时间复杂度是 O(m n)空间复杂度 O(1)。这个解法在 74 题里完全适用而且如果你之后做到 240 题会惊喜地发现同一个模板直接就能用。因为它只依赖“每行从左到右递增、每列从上到下递增”这两个条件而 74 题恰好同时满足这两个条件。我个人的体会是如果你想在时间和空间上找一个“稳妥万能”的解法右上角线性搜索是面试中最容易讲清楚、也最不容易写错的方案。它比一次二分稍慢但比暴力快得多而且代码几乎不需要动脑去边界条件。4. 解法三两次二分先定位行再定位列4.1 第一次二分如何锁定目标可能所在的行既然矩阵每一行的首元素是递增的那么我们可以先对“每一行的首元素”做一次二分找到最后一行首元素小于等于 target 的行。这一步的本质是在行首元素数组里找 target 的 upper_bound 位置的前一个。这样说可能有点绕直接举例。还是拿刚才那个 3 x 4 的矩阵行首元素分别是 [1, 10, 23]。假设 target 是 16行首元素中 10 是最后一个小于等于 16 的数所以 target 如果存在只可能在第二行。假设 target 是 30最后一个小于等于 30 的是 23所以候选行是第三行。假设 target 是 0没有任何行首元素小于等于 0直接返回 false。第一次二分的终止条件要特别注意我们要找的是“最后一个 target”的位置而不是随便一个 target 的位置。常规的二分查找写法需要稍微调整用左闭右开或者记录 ans 的方式都可以。4.2 第二次二分在目标行内搜索锁定目标行之后问题就退化成了“在一个普通的一维有序数组里查找 target”这就是标准二分的主场了。对目标行做一次常规的二分查找找到就返回 true找不到返回 false。这个方法的时间复杂度是 O(log m log n)也就是 O(log(m * n))已经是对数级别的复杂度。相比一次二分见下节它更符合人的直觉因为分了两步先纵向定位再横向定位。4.3 代码实现与边界条件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]) # 第一次二分找最后一个 target 的行首元素所在行 left, right 0, m - 1 while left right: mid (left right 1) // 2 if matrix[mid][0] target: left mid else: right mid - 1 row left # 如果 target 比该行第一个元素还小可以直接返回 false if matrix[row][0] target: return False # 第二次二分在目标行内查找 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 False这里最容易写错的是第一次二分。因为我们要找的是“最后一个小于等于 target 的数”如果用普通的mid (left right) // 2很容易陷入死循环。我这里用了(left right 1) // 2也就是向上取整。为什么要向上取整因为当left和right相邻时比如 left0, right1如果向下取整mid0更新 left0 会导致区间不收缩就死循环了。向上取整则保证了每次更新后区间一定收缩。5. 解法四一次二分把二维矩阵直接拍扁成一维5.1 核心思想与逻辑映射这个解法是 74 题的最优解也是最值得掌握的写法。前面我们已经分析过这个矩阵满足“行间行内全部递增”所以它可以被拉平成一个长度为 m * n 的严格递增一维数组。关键问题在于我们没有一个真实的一维数组。但没关系我们可以用数学映射把一维下标映射回二维坐标。假设矩阵有 m 行 n 列一维数组下标从 0 到 m * n - 1。给定一个一维下标 mid它对应的二维坐标是行号 row mid // n列号 col mid % n这个映射关系很直观每 n 个元素组成一行商就是行号余数就是列号。举个例子一个 3 x 4 的矩阵一维下标 5 对应 row 5 // 4 1col 5 % 4 1也就是 matrix[1][1]正好是 11符合预期。有了这个映射我们剩下的操作就和普通一维二分完全一致维护 left 和 right 两个指针计算 mid取出 matrix[mid // n][mid % n] 和 target 比较然后移动左右指针。5.2 代码实现与复杂度分析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 num matrix[mid // n][mid % n] if num target: return True elif num target: left mid 1 else: right mid - 1 return False时间复杂度是 O(log(m * n))空间复杂度是 O(1)。这也是这个题能达到的最优复杂度因为在一个有序数组中查找对数下界就是这么多。我自己在实际写这个解法时踩过一个特别傻的坑把mid // n和mid % n写反结果行列坐标永远不对。所以强烈建议每次写完映射后用一个小矩阵手动验证一次比如 3 x 4 的矩阵手动检查 mid 0、mid 3、mid 4、mid 11 这几个关键点的映射对不对。6. 四种解法横向对比与进阶变体6.1 复杂度和适用场景对比表解法时间复杂度空间复杂度适用题目代码难度暴力遍历O(m * n)O(1)任意矩阵极低右上角线性搜索O(m n)O(1)74、240 通吃低两次二分O(log m log n)O(1)仅 74中一次二分O(log(m * n))O(1)仅 74中从复杂度上看一次二分最优从通用性上看右上角线性搜索最优。面试中我建议你优先讲一次二分因为对 74 题来说这是最贴合“矩阵全局有序”这个特性的最优化思路。但如果面试官追问“如果去掉行首大于上一行行尾的条件怎么办”这时候就要转向上角线性搜索。6.2 如何从 74 题迁移到 240 题LeetCode 240 题“搜索二维矩阵 II”是 74 题最常见的面试延伸题。240 的矩阵只保证每行递增、每列递增并不保证上一行的最后一个数小于下一行的第一个数。举个例子[1, 4, 7, 11] [2, 5, 8, 12] [3, 6, 9, 16]这里第一行最后一个是 11第二行第一个是 2显然不满足全局递增。所以一次二分的思路直接失效因为你不能把矩阵拉成一个有序一维数组。但右上角线性搜索依然成立因为它只要求“左小下大”。这也是为什么很多老师会建议两道题放一起刷先做 74 再 240体会从强条件到弱条件的解法变化。74 题练的是“如何利用更强的有序性做二分”240 题练的是“如何在部分有序中找排除规则”。顺带一提“爱吃香蕉的狒狒”LeetCode 875这类题和本题同属二分法的变体只不过它的核心是“对速度值做二分再验证可行性”。和二分的思维迁移有关但题型离得更远这里不展开。7. 实际刷题中的高频 Bug 与调试心得7.1 空矩阵与空行的防御性判断这道题最容易被忽略的边界条件是空输入。如果 matrix 是空的或者 matrix[0] 是空的那么任何取 len(matrix[0]) 的操作都会报错。我见过不少人在 LeetCode 上提交代码一上来就n len(matrix[0])然后测试用例给一个空矩阵直接 IndexError。稳妥的写法是在函数最开头就加防御性判断if not matrix or not matrix[0]: return False这行代码同时处理了“行数为空”和“列数为空”两种极端情况。别小看这一行它省去了后面所有对矩阵形状的假设。7.2 整数溢出与 mid 的求法严格来说Python 的整数不会溢出所以这个问题只在 C、Java 这类语言里存在。在 C 中如果 left 和 right 都接近 INT_MAX(left right) / 2可能溢出。更安全的写法是int mid left (right - left) / 2;这个写法的原理是避免先加后除导致越界。虽然在这道题里 left 和 right 最大也就 m * n - 1一般不会溢出但这是一个良好的代码习惯面试官看到这种写法通常会加分。7.3 二分死循环的判定与修复二分最容易出 bug 的场景就是死循环。虽然本题的标准二分写法比较简单但在两次二分解法里第一次二分很容易写死循环。前面我提过用mid (left right 1) // 2来避免区间不收敛的问题。再分享一个通用调试技巧当你不确定二分终止条件写得对不对时直接在纸上模拟一个长度为 2 的区间比如 left0, right1看你的 mid 取整方向能不能让 left 或 right 发生变化。如果 left 始终不变必然是死循环如果 right 始终不变也必然是死循环。这个技巧能帮你快速定位 90% 以上的二分问题。7.4 用断言和示例矩阵自测映射关系如果你选择一次二分解法强烈建议在本地写一个简单的自测函数验证映射关系的正确性。比如def test_mapping(): m, n 3, 4 for idx in range(m * n): row idx // n col idx % n print(idx, -, row, col)跑一遍你就会发现规律非常清晰0 - (0,0)3 - (0,3)4 - (1,0)11 - (2,3)。把这种映射关系在头脑里建立肌肉记忆后写一次二分就再也不会因为坐标算错而返工。8. 面试时可以借鉴的高分表达框架8.1 从暴力到最优的思考路径展示面试遇到这题我最推荐的答题顺序是先说暴力思路然后迅速过渡到有序性带来的优化空间。具体话术可以是这样的“这道题我先想到的是暴力遍历 O(m * n)但是题目给了两个关键条件行内递增且行间递增说明整个矩阵本质上是一个有序一维数组的二维形态。所以我可以把二维下标映射成一维下标直接做一次二分时间复杂度 O(log(m * n))。”然后直接写一次二分的代码。写完代码后再补充边界条件比如空矩阵、映射关系是怎么来的。这种表达方式展示了从暴力到最优的完整思考链路面试官最想看到的就是这种“优化能力”的呈现而不只是一个正确答案。8.2 说清楚“为什么这个解法是对的”很多候选人在面试时能写出正确代码但讲不清楚正确性。至少要把下面三个点讲明白第一为什么矩阵可以展开成有序一维数组因为行内递增且上一行行尾小于下一行行首所以按行拼接后全局有序。第二为什么 mid 的映射是 row mid // n、col mid % n因为每一行固定有 n 个元素整除和取余正好把一维下标切分成二维坐标。第三为什么二分不会漏掉元素因为一维数组是有序的而二分法基于有序性每次排除一半最终收敛到目标或确认不存在。把这三个逻辑闭环说清楚这道题才算真正答透了。9. 刷题之外的一点延伸思考这道题给我的最大启发其实不是“会写二分”而是“识别数据结构中隐藏的全局有序性”。很多看似是二维的问题一旦发现行间行内的递进关系就可以降维成一维问题。这种降维思维在算法题里太常见了比如矩阵前缀和、矩阵快速幂、图的最短路建模本质上都是在做类似的抽象。回到实践层面如果你正在准备面试建议把 74 题和 240 题放在同一天刷先自己写一遍然后对照题解检查边界条件。刷完以后试着不看代码纯手写在纸上写出一次二分解法再默写一遍右上角线性搜索解法。这两套代码都值得形成肌肉记忆因为它们一个代表“最强有序性的利用”一个代表“部分有序性的通用解法”。关于 74 题我最后补充一个自己刷题时踩过的坑最开始我图省事直接把 240 题的右上角解法套到 74 题上交了虽然能过但时间复杂度不是最优的。后来认真想明白一次二分之后才意识到自己漏掉了题目里最关键的“全局有序”这个信息。所以建议大家做这题时一定先把两种解法的适用场景区分清楚别上来就套模板。