企业官网建设流程全解析

1. 先别急着写代码：这道题到底在考什么

1.1 两道“搜索二维矩阵”，别搞混了

LeetCode上叫“搜索二维矩阵”的题其实有俩。一道是第74题，矩阵满足两个条件：每一行从左到右递增，且每一行的第一个整数都比上一行的最后一个整数大。也就是说，整个矩阵从左上角到右下角，按行展开之后是一个严格递增的一维数组。

另一道是第240题，叫“搜索二维矩阵 II”，条件变成了：每一行从左到右递增，每一列从上到下递增，但整体不保证是“一维有序数组”的形状。比如矩阵第一行的最后一个数是5，第二行的第一个数可能是3，展开成一维数组之后并不是全局有序的。

很多人刷题的时候以为这俩差不多，直接套用一个解法，结果要么超时要么边界错。这俩题放在一起看才比较完整，它们正好代表了两种不同的“有序性”：74题是全局有序，240题是行列各自有序。面试里追问的时候，这两道题经常被放在一起比较，所以刷的时候最好一起拿下。

1.2 为什么搜索二维矩阵能进热门100题

这道题能进LeetCode热门100题，不是因为它难，而是因为它太有代表性。它考察的是一个很核心的能力：把一维有序数组上的二分查找，迁移到二维结构上。很多人二分查找刷得挺熟，但一放到矩阵里就不会做了，本质上还是没有理解二分到底在利用什么——利用的是“数据的单调性”可以帮我们砍掉一半搜索空间，而不是死记模板。

另外，这道题还牵扯到一个非常基础又关键的技巧：一维索引与二维坐标的互相转换。这个映射关系在后续做动态规划、图遍历、矩阵压缩存储的时候都会用到。我见过很多人卡在这一步，不是不会二分，而是不会把 mid 换算成 row 和 col。这也是为什么这道题被归为“数据结构-矩阵”与“算法-二分查找”的交汇点。

1.3 最优解法不止一种，但核心都是二分

74题的最优解是二分，方法有两种：一次二分把矩阵拍平，或者两次二分先找行再找列。240题的最优解是从右上角出发“走楼梯”，也叫Z字搜索，每次排除一行或一列。前者复杂度是 O(log(mn))，后者是 O(m+n)。

面试的时候，我习惯先从暴力解法讲起，再逐步优化到二分。这样面试官能看到你完整的思考链路，而不是背答案。接下来把这几种解法挨个拆开，每种的思路、代码、坑都讲一遍。

2. 从O(mn)到O(log(mn))：三种解法逐一拆解

2.1 解法一：暴力遍历，复杂度O(mn)

暴力解法没什么技术含量，就是两层循环，遍历所有元素，找到target就返回True，全部遍历完没找到就返回False。代码大概长这样：

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

别急着嘲笑这个方法。暴力法有一个实际价值：当你写优化版解法的时候，可以用它来验证结果是否正确。尤其是边界情况很多的时候，拿暴力法当基准测试，能帮你快速定位是二分逻辑的问题还是坐标转换的问题。我在本地调试的时候经常这么干，写一个简单的测试脚本，把暴力结果和二分结果对比，一秒钟就能发现逻辑错误。

另外，面试里如果矩阵特别小，比如 2x2 或者 3x3，暴力法不一定比二分慢，因为二分常数项更高。这个点你可以提一嘴，能体现你不是背题，而是真的在考虑工程权衡。

2.2 解法二：两次二分，先确定行再确定列

两次二分很好理解：第一次二分，找到“最后一个首元素小于等于 target”的那一行，第二次二分，在那一行里做标准一维二分。这种解法比较符合直觉，不容易出错。

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]) # 第一次二分：找到最后一个满足 matrix[top][0] <= target 的行 top, bottom = 0, m - 1 while top < bottom: mid = (top + bottom + 1) // 2 if matrix[mid][0] <= target: top = mid else: bottom = mid - 1 row = top # 第二次二分：在该行内查找 target 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

这里有一个细节值得注意。第一次二分用的是“寻找右边界”的模板，即找最后一个满足条件的值，所以 mid 要写成(top + bottom + 1) // 2，也就是向上取整，否则会在只剩两个元素的时候陷入死循环。这个问题我在 4.1 里展开说。如果你对二分模板还不太熟，建议先把标准二分查找和“找左边界/右边界”两个模板练透，再来写这题，不然很容易在第一次二分那里栽跟头。

2.3 解法三：一次二分，把二维数组拍平

因为74题的矩阵整体有序，所以可以把它想象成一个长度为 m*n 的一维有序数组。每次拿到一维索引 mid，通过row = mid // n、col = mid % n转换成矩阵里的坐标，然后照常比较。

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 - left) // 2 val = matrix[mid // n][mid % n] if val == target: return True elif val < target: left = mid + 1 else: right = mid - 1 return False

这个解法代码非常短，但需要真正理解坐标映射的原理。mid // n得到的是行号，mid % n得到的是列号。注意是除以列数 n，不是行数 m，这个很多人会搞反。举个例子，一个 3 行 4 列的矩阵，一维索引是 0 到 11。当 mid = 5 时，5 // 4 = 1表示第 1 行，5 % 4 = 1表示第 1 列，对应矩阵里第二行第二列的元素。为什么行列都是从 0 开始数，因为一维索引也是从 0 开始的，取整和取模天然对齐。

2.4 三种解法对比与选型建议

注意，log(mn) 和 log m + log n 在数学上是相等的，所以两种二分的时间复杂度没有本质区别。面试里两种都可以写。我的建议是：如果面试官没有特别要求，优先写一次二分，因为代码短、逻辑清晰，展示你对有序结构的理解；如果你自己对二分模板还不够熟练，写两次二分更稳妥，因为每一步都比较直白，不容易出 bug。

另外有一个点可以提：两次二分第一次是在行首数组上二分，如果矩阵的行数远大于列数，或者反过来，两种二分的实际效率在常数上有微小差异，但对算法题来说不必纠结。

3. 代码实现中的关键细节和实战技巧

3.1 一维索引与二维坐标的映射关系

这部分是这道题的灵魂。row = mid // n、col = mid % n这个公式，我见到不止一个同学在面试现场写错。最常见的错误是把 n 写成 m，导致 row 和 col 反转，查出来的值完全不对。

记忆方法很简单：一维数组是按行展开的，每个“块”的大小是列数 n。也就是说，每走 n 步才换一行。所以除 n 得到行号，模 n 得到列号。你可以想象一下电影院座位，一排有 n 个座位，你从 0 号座位开始数，座位 5 在第几排第几座？就是5 // n排，5 % n座。这个类比我百试不爽，讲给朋友听都秒懂。

如果你是用两次二分解法，不需要这个映射，但也需要理解矩阵的行列索引关系。比如matrix[row][col]，row 是行下标，col 是列下标，取值分别是 0 到 m-1 和 0 到 n-1。不管哪种解法，动手写代码之前先在草稿纸上画一个 3 行 4 列的矩阵，把一维索引标上，再自己推一遍 mid=5、mid=7、mid=11 分别对应哪个元素。这个习惯能帮你避免大部分低级错误。

3.2 二分循环的边界条件：while left < right 还是 <=

这是二分查找里最经典的问题。标准做法是：如果你使用的是左闭右闭区间，也就是 left 和 right 都指向可能的值，那么循环条件是left <= right；如果你使用的是左闭右开区间，也就是 right 指向下一个不可能的位置，那么循环条件是left < right。

我在这道题里推荐左闭右闭。原因很简单：right 初始化为m * n - 1，即最后一个元素的下标，mid 也用left + (right - left) // 2计算，最后退出时 left > right，逻辑最直观。在 2.3 的代码里，我用的就是left <= right。

还有一个细节，mid = left + (right - left) // 2和mid = (left + right) // 2在数学上一样，但前者避免了 left + right 整数溢出。虽然 Python 的 int 没有溢出问题，但是在 Java 和 C++ 里，如果 left 和 right 都是很大的数，left + right 有可能会超过 int 上限。这个细节是面试官很喜欢追问的，也是一个能体现工程经验的小点。

3.3 判空与边界测试：一个都不能少

这道题有一个非常经典的坑：空矩阵。LeetCode 的测试用例里，matrix = []和matrix = [[]]两种情况都会出现。

• 当matrix = []，matrix[0]会直接报 IndexError。
• 当matrix = [[]]，len(matrix[0]) = 0，如果你没判not matrix[0]，后续操作会出问题。

所以标准的判空写法是：

if not matrix or not matrix[0]: return False

这个写法同时处理了两种情况。not matrix过滤掉空列表，not matrix[0]过滤掉“有行但没列”的情况。我建议你在写任何矩阵相关的算法题时，都默认加上这个判断，养成肌肉记忆。

边界测试除了空矩阵，还建议测这几个用例：

• 单行矩阵：[[1, 3, 5, 7]]，target 在行中、行首、行尾、比所有数大、比所有数小。
• 单列矩阵：[[1], [3], [5]]，target 在列中、列首、列尾、不存在。
• 目标值等于矩阵第一个元素、最后一个元素。
• 目标值不存在但介于某两个数之间。

这些用例覆盖了二分查找的所有分支路径。我一般写完代码后不会直接交，而是先用这几个用例本地跑一遍，确保没问题再提交。

3.4 Python/Java/C++三种写法的差异

Python 版本我已经在 2.3 里给出完整代码了，这里重点说一下另外两种语言需要注意的点。

Java 版本，需要注意整数溢出问题，所以 mid 必须写成left + (right - left) / 2。另外 Java 的二维数组定义是int[][] matrix，判断空矩阵要写matrix.length == 0 || matrix[0].length == 0。

public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) { return false; } int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while (left <= right) { int mid = left + (right - left) / 2; int val = matrix[mid / n][mid % n]; if (val == target) { return true; } else if (val < target) { left = mid + 1; } else { right = mid - 1; } } return false; }

C++ 版本，需要注意vector<vector<int>>的引用传递，避免拷贝整个矩阵。另外，m * n可能会溢出，如果 m 和 n 都是 int 类型，在某些极端情况下相乘可能超过 INT_MAX，所以可以改成long long total = (long long)m * n，或者直接用left和right分别记录行列的乘积。

bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) { return false; } int m = matrix.size(), n = matrix[0].size(); int left = 0, right = m * n - 1; while (left <= right) { int mid = left + (right - left) / 2; int val = matrix[mid / n][mid % n]; if (val == target) { return true; } else if (val < target) { left = mid + 1; } else { right = mid - 1; } } return false; }

这三种写法逻辑完全一样，区别只在语言特性。面试时你用什么语言不重要，重要的是你能把边界条件、溢出问题和坐标转换讲清楚。

4. 刷题和面试中真实踩过的坑

4.1 死循环的排查实录

我第一次写两次二分解法时，第一次二分用了一个错误的模板，导致死循环。当时代码长这样：

while top < bottom: mid = (top + bottom) // 2 if matrix[mid][0] <= target: top = mid else: bottom = mid - 1

当矩阵只剩两行、且 target 位于较上面的行时，假设top=0, bottom=1，算出mid = (0+1) // 2 = 0，如果matrix[0][0] <= target，那么top = mid = 0，top 没有前进，下一次循环还是top=0, bottom=1，陷入死循环。

排查方法很简单，在循环里打印top、bottom、mid的值，看到三者不再变化，就说明 mid 的计算方式有问题。解决办法是把 mid 改成向上取整：

mid = (top + bottom + 1) // 2

这样当top=0, bottom=1时，mid = 1，循环能够正常退出。总结一下：当更新方式是left = mid（不是left = mid + 1）时，mid 必须向上取整；当更新方式是right = mid时，mid 可以向下取整。这个规则能覆盖大部分二分边界问题。

4.2 240题用74题解法直接写，结果超时

刷完74题之后，很多人会顺手去写240题，想着“我都写了一次二分，这题还不是手到擒来”。结果一交，发现要么答案错误，要么超时。

原因很简单：240题不满足全局有序，矩阵展开后不是递增数组。比如：

[[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 13]]

第一行末尾是11，第二行开头是2，展开后 11 > 2，逆序了，所以一次二分根本没法用。正确解法是“走楼梯”：从右上角开始，如果当前值等于 target，返回 True；如果当前值大于 target，说明这一列剩下的都更大，列指针左移；如果当前值小于 target，说明这一行左边的都更小，行指针下移。

def searchMatrix(self, matrix, target): 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: if matrix[row][col] == target: return True elif matrix[row][col] > target: col -= 1 else: row += 1 return False

这个方法的直观理解是：右上角是整个矩阵的“拐点”，它左边的都比它小，下边的都比它大。根据 target 和当前位置的大小关系，每次都能排除一行或一列，所以复杂度 O(m+n)。面试里如果被问到“能不能再快一点”，答案是不能，因为如果矩阵只有行列有序，理论上需要至少 O(m+n) 才能找到或排除。

4.3 如何写出一份“面试官友好”的题解

很多同学以为写出正确代码就够了，其实面试官更在意你会不会解释“为什么这么做”。我建议按照这个顺序讲：

第一，先说暴力法，告诉面试官复杂度是 O(mn)，但确认这是个可行的保底方案。第二，指出矩阵的“有序性”特点，说明这个问题可以二分。第三，手推坐标映射公式，解释mid // n和mid % n的来源。第四，分析边界条件和复杂度，说明为什么是 O(log(mn))。

这套话术不是背题，而是让你在面试里更从容。我曾经在模拟面试中见过一个候选人，代码写对了，但面试官问他“为什么 mid 要除以列数 n”，他答不上来，面试官只能降低评价。所以一定要理解到“每个换算的底层逻辑”这一层，而不是背模板。

4.4 用“搜索二维矩阵”串起一整个二分专题

刷完这题之后，我强烈建议把下面几道题放到一起做，因为它们都是“利用有序性排除搜索空间”的变体：

• LeetCode 704 二分查找：最基础的一维二分，先把这个写熟。
• LeetCode 33 搜索旋转排序数组：数组被旋转了，但依然可以用二分找到目标值。
• LeetCode 153 寻找旋转排序数组中的最小值：同样是旋转数组，要找的是最小值的位置。
• LeetCode 162 寻找峰值：不完全是单调，但可以二分。
• LeetCode 240 搜索二维矩阵 II：行列有序矩阵的Z字搜索。

把这组题刷完，你会对“二分”有更深的理解，而不再是背模板。我自己的体会是，二分查找不是一种模板，而是一种思维方式：“当前搜索范围有一部分肯定没有答案，把它砍掉。”理解了这一点，所有变形题都是纸老虎。

5. 延伸思考：这个问题在真实业务中的样子

5.1 有序数据集上的范围查询

算法题看起来离业务很远，但其实“搜索二维矩阵”在真实系统里能找到影子。我举一个做过的例子：监控系统里，每台机器按时间戳记录指标数据，数据存储在类似“机器 x 时间”的二维表结构里。查询某个时间戳有没有异常数据，如果机器按固定顺序排列，且每台机器的时间序列都是递增的，其实就是一个74题的结构，可以用一次二分定位到机器，再二分定位到时间。

反过来，如果不同机器之间的时间戳没有大小关系，只保证每台机器内部有序，那这就是240题的结构，需要逐行二分或者走楼梯。当时我们的存储层为了查询效率，特意把机器维度做了排序，让整体满足“上一台机器最后一条记录的时间戳小于下一台机器第一条记录的时间戳”，就是为了让查询从 O(m log n) 降到 O(log(mn))。

这种“为了查询而精心设计数据排列”的思路，在数据库索引、LSM-Tree、列式存储设计里都非常常见。算法题里的“有序性”，本质上就是在为工程里的查询优化做铺垫。

5.2 从“能否找到”到“找到最左/最右位置”

如果面试官继续追问，问题会变得更难一些：矩阵里有重复值怎么办？如果 target 出现多次，怎么找到第一次或最后一次出现的位置？

这个问题其实是把74题从“存在性查询”升级为“范围查询”。解法也不复杂：第一次二分找行的时候，用“找左边界”的方式；行内二分也用“找左边界”的方式；一次二分解法的话，直接变成“在拍平的一维数组上找左边界”。复杂度还是 O(log(mn))，代码改动也不大，但思考维度一下子深了。

很多业务的“查一条记录是否存在”其实并不常见，更常见的是“查某个范围内的所有记录”。比如日志系统里查“下午 3 点到 5 点之间的所有错误日志”，这本质上就是在有序数组上做两次边界二分，找到左边界和右边界，然后切片。这也是面试官特别喜欢把“查找边界”作为追问方向的原因，因为它更贴近工程。

5.3 空间换时间的整体思路

如果你需要反复查询同一个矩阵，每次都做二分显然不是最优的。更工程的做法是做预处理：

• 把矩阵的每一行行首元素单独拉出来，构建一个有序数组，配合二分。
• 或者直接把所有元素存入哈希集合，查询时 O(1) 判断是否存在。
• 如果矩阵太大放不进内存，还要考虑分块加载、外部排序、布隆过滤器过滤等方案。

这些方案的核心是空间换时间。实际工程里没有银弹，查询频率、矩阵大小、数据更新频率决定了你该选哪种策略。算法题里通常不讨论这种权衡，但面试官可能顺嘴问一句，你如果能从工程角度回答，印象分会很高。

我个人的经验是，当你刷题刷到一个“查询型”问题，可以多问自己一句：如果这个操作要做一万次，我的解法还行吗？这个简单的追问，能帮你把算法思维和工程思维结合起来，这也是高级工程师和初级的差异所在。

5.4 一个问题带出整片知识网

最后说点我自己的刷题体会。搜索二维矩阵这道题，我前前后后刷了不下五遍。不是因为我记性差，而是每次隔一段时间重刷，都会发现自己对二分检索、边界处理、坐标转换的理解又深了一点。

第一遍刷，我只会暴力法；第二遍学会了两次二分；第三遍能写一次二分，但坐标转换偶尔写错；第四遍终于把边界条件和溢出问题彻底吃透；第五遍开始主动归纳旋转数组、找峰值、找边界这些衍生题。这个过程对我自己的成长帮助很大。所以如果你现在觉得题目难，别急，把它放进收藏夹，隔一个月再写一遍，感受完全不一样。