企业官网建设流程全解析

前几天我把力扣热题100（Hot100）里二分相关的题集中过了一遍，做到“搜索二维矩阵”时反而花了最多时间复盘。题目本身一句话就能说清楚：给你一个 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(m+n)。

所以面试时，看到这种题先别急着写代码，先把题目的条件翻译成一句：“整个矩阵展开是一个有序数组”，这就已经赢了一半。很多时候面试官考察的并不是你能不能写对二分，而是你有没有意识到这个全局有序性决定了算法能达到什么级别。

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 时：

• 初始 left=0, right=2；
• mid=1，matrix[1][0]=10，10 <= 11，所以 left=2；
• 此时 left=2, right=2，mid=2，matrix[2][0]=23，23 > 11，所以 right=1；
• 退出循环，right=1，row=1，正确。

推这一遍以后，你对这块的判断就不容易再错了。

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 False

2.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，但列数 n=0，后面所有索引访问都会越界。

这个细节虽然简单，但我给不少人 review 代码时发现，真的有人会因为漏掉not matrix[0]而在白板面试上卡壳。不要觉得这是小事，工程意识的考察往往就在这种地方。

3. 解法二：把二维矩阵拉直成一个虚拟有序数组

3.1 从全序条件到“一维化”

解法一很直观，但它需要两个二分循环。解法二则更进一步：既然矩阵展开后就是一个递增数组，那我可以直接把这个数组当成一个逻辑上的一维数组来做二分。

但矩阵本身还是二维存储的，所以需要一个“一维下标 -> 二维坐标”的映射：

• 行号：mid // n
• 列号：mid % n

注意这里是对列数n取模，不是对行数m。很多人在这个地方写反，我用一个小例子验证一下：

假设 m=3, n=4，一维下标 mid=6。对应展开序列的第 6 个元素（从 0 开始数）。6 // 4 = 1，6 % 4 = 2，对应矩阵第 1 行第 2 列，即值为 16 的位置。我们验证展开序列：索引 0=1, 1=3, 2=5, 3=7, 4=10, 5=11, 6=16，完全对得上。

这个映射的本质是：一维下标先按每行元素个数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 两种解法对比：面试时怎么选

我个人的建议是：面试时先讲解法一，因为它的思路直观，容易让面试官跟上你的节奏；然后提一句“其实因为矩阵本身满足全局递增，还可以直接把下标映射成一维数组做一次二分，代码更简洁”，顺手把解法二写出来。这样既展示了你的基础功底，又展示了你在“有序性”上的敏感度。

如果你是在刷题阶段看这篇，我更推荐主练解法二。因为它省掉了行定位那一步的判断，写起来快，也不容易在边界条件上翻车，特别适合面试高压状态下 5 分钟内写完的场景。

4. 边界条件、测试用例与常见翻车点

4.1 一组值得反复跑的最小用例

刷题最怕的是“用例过了就以为过了”，其实很多隐藏问题都藏在边界里。我每次写这类二分题，都会拿下面这组用例快速过一遍：

尤其是“单行”和“单列”这两种形状，最容易暴露m和n用混的问题。比如解法二里，如果手滑把mid % n写成mid % m，在 m=3, n=4 这种矩阵上就直接算错；但如果 m=n=1，或者 m=n=2，你甚至可能侥幸跑过几个用例。所以刷题时一定要主动拿非方阵去测。

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 小于所有元素：二分不断缩右边，最后 left=0, right=-1，循环退出，返回 false。此时没有任何越界风险。
• target 大于所有元素：二分不断缩左边，最后 left=mn, right=mn-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，并不是有序的。target=2 时，如果你用一次二分：mid=(0+3)//2=1，对应元素 3，因为 3 > 2，你会把右半部分舍弃，搜索区间变成 [0,0]，于是错误地返回 false——但 2 明明在矩阵里。

所以，在 240 题里，解法二的“一维化二分”完全不可用。你必须在“行 / 列分别有序”的局部性质上重新设计搜索路径。

5.2 Z 字形搜索为什么是 O(m+n)

从右上角出发，是一个经典做法。设当前坐标为 (row, col)，初始 row=0, col=n-1：

• 如果 matrix[row][col] == target，直接返回 true；
• 如果 matrix[row][col] > target，说明当前这一列下方所有元素都大于当前值，一定大于 target，所以整列都可以排除，col 左移；
• 如果 matrix[row][col] < target，说明当前这一行左侧所有元素都小于当前值，一定小于 target，所以整行都可以排除，row 下移。

因为每次操作都能排除一整行或一整列，所以最坏情况下走 m+n 步就到边界，复杂度是 O(m+n)。

Z 字搜索之所以从右上角开始，而不是左上角，是因为左上角是矩阵最小值的位置，往右往下都比它大，你没法决定往哪个方向走；右下角同理。右上角是一个天然的“分界点”：左边都比它小，下边都比它大，刚好能根据 target 与当前值的大小决定唯一的移动方向。

5.3 这道题在 Hot100 二分题单里的位置

如果你是按专题刷 Hot100，可以顺手把这几道题放在一起对比：

• 搜索二维矩阵（本题）：全局有序，一维二分即可；
• 搜索二维矩阵 II（240 题）：行列分别有序，Z 字搜索 O(m+n)；
• 搜索旋转排序数组：局部有序，需要先判断哪一半有序再二分；
• 在排序数组中查找元素的第一个和最后一个位置：二分的边界语义，lower_bound / upper_bound；
• 寻找峰值：不是直接找 target，而是根据相邻关系判断上升 / 下降趋势。

这些题本质都是在问同一个问题：搜索区间是否单调，每一步能稳定排除掉哪一片。你会发现二分模板本身并不难，难的是“是否具备二分条件”以及“区间收缩后 target 位于哪一半”这两个判断。把“搜索二维矩阵”吃透，尤其是理解“全序展开”这个视角，后面做旋转数组、找峰值，很多思路都能复用。

我个人现在刷 Hot100 二分专题的习惯是：每道题先花 30 秒在纸上画一下结构和搜索顺序，再动手写循环。尤其是这类“二维嵌套有序”的题，花在判断单调性上的时间，永远比写代码的时间更值钱。这道题我至少给不同的人讲过三遍，每次讲到最后都会发现，真正让别人卡住的不是二分本身，而是没有意识到“矩阵拉直后就是一个数组”这个隐藏条件。希望这篇复盘，也能帮你把这一层窗户纸捅破。