企业官网建设流程全解析

刷 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 为什么从右上角开始而不是左上角

很多第一次接触这道题的人会困惑：既然矩阵有序，为什么不从左上角开始搜？我们可以推演一下：假设从左上角开始，当前位置是 1，target 是 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相邻时，比如 left=0, right=1，如果向下取整，mid=0，更新 left=0 会导致区间不收缩，就死循环了。向上取整则保证了每次更新后区间一定收缩。

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 = 1，col = 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 复杂度和适用场景对比表

从复杂度上看，一次二分最优；从通用性上看，右上角线性搜索最优。面试中我建议你优先讲一次二分，因为对 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 的区间，比如 left=0, right=1，看你的 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 题上交了，虽然能过，但时间复杂度不是最优的。后来认真想明白一次二分之后，才意识到自己漏掉了题目里最关键的“全局有序”这个信息。所以建议大家做这题时，一定先把两种解法的适用场景区分清楚，别上来就套模板。