LeetCode 74 搜索二维矩阵：一次二分查找的核心思路与边界处理

1. 先把题读懂：搜索二维矩阵到底在考什么

后台经常有人问我，LeetCode Hot 100 里那么多题，先刷哪些性价比最高？我的答案里永远有第 74 题“搜索二维矩阵”。题目本身不复杂，但它把二分查找、二维坐标映射、边界条件处理三个基本功一次性考到位了，而且代码量极短，非常适合作为“二分查找”这个专题的入门题。

1.1 题面信息提炼

原题的大致描述是这样的：给你一个 m x n 的整数矩阵 matrix 和一个目标值 target，矩阵满足两个条件：

• 每一行的元素从左到右递增；
• 每一行的第一个元素都比上一行的最后一个元素大。

换句话说，如果你把矩阵的每一行依次首尾相接，拉成一个一维数组，这个一维数组是整体有序的。题目要求你在这个矩阵中判断 target 是否存在，并且期望的时间复杂度是 O(log(m * n))。

这个条件比另一道同样出现在 Hot 100 里的“搜索二维矩阵 II”（LeetCode 240）要强得多。240 题只保证“每行从左到右递增、每列从上到下递增”，并不保证整个矩阵按行拉直后有序。74 题借助“行尾和下一行行首依然衔接有序”这个额外性质，把二维问题降维成了一维问题。

1.2 为什么这道题能进 Hot 100

Hot 100 的题单不是随便排的，它把各大厂面试出现频率高、覆盖面广的题目挑了出来。74 题虽然难度标的是 Medium，实际实现难度更接近 Easy，但它能稳定出现在各类高频题单里，原因有三。

第一，二分查找本身就是面试重灾区，而很多候选人只能背出“在有序数组里找一个数”的模板，一放到二维结构里就懵了。74 题正好检验你能不能把二维坐标转换成一维下标。

第二，题目允许你用“先找行、再找列”的两次二分，也允许你用“一次二分映射下标”，两种写法暴露出来的思路差异很大，面试官很爱从这里追问你对于复杂度的理解。

第三，它和 240 题、33 题（搜索旋转排序数组）能串成一条“有序结构查找”的完整链路，刷一道等于给后面好几道题打底子。

个人建议把它放在 Hot 100 刷题计划中“二分查找”分类的第一周完成。别想复杂，先把一次二分的版本写顺。

2. 核心思路：为什么二维矩阵可以当成一维数组来搜

2.1 单调性是这道题的命门

判断一道“查找类”题目能用什么算法，先看数据组织方式是否具备单调性。

单调性指的是：存在某种遍历顺序，让序列中的元素整体保持递增或递减。一维有序数组天然具备。74 题的矩阵不一样，它由行和列两个维度组成，虽然每行递增、每列递增，但如果行与行之间没有衔接关系，就无法确定一个全局顺序。比如 240 题的矩阵：

1 4 7 2 5 8 3 6 9

如果按行拉直是 [1,4,7,2,5,8,3,6,9]，这显然不是有序的。所以 240 题不能用一次二分。而 74 题明确给出了“每行第一个数 > 上一行最后一个数”的条件，这等于告诉你可以把矩阵“拉直”。

我习惯用一个火车车厢的类比来解释：每节车厢里座位号从左到右递增，而且下一节车厢第一排的起始号一定大于上一节最后一排的末尾号。那么整列车的座位号就是全局递增的。你买了一张票，要找座位，不需要一节一节换着找，直接用全局二分定位就好。

2.2 二维下标与一维下标怎么换算

既然可以把矩阵拉直，就需要建立“一维下标 -> 二维坐标”的映射关系。设矩阵有 m 行、n 列，行下标从 0 到 m-1，列下标从 0 到 n-1。如果我们将矩阵按行展开成一维数组，一维下标 index 的范围是 0 到 m*n-1，那么：

• 行号 row = index / n（整除）
• 列号 col = index % n（取余）

比如 3 行 4 列的矩阵，index = 5 对应的位置是第 5 / 4 = 1 行，第 5 % 4 = 1 列，也就是第二行第二列。这个换算是整个算法的核心，很多人出 bug 都是因为把 n 写成了 m。

这里有一个很好记的口诀：除法看是哪一行，取余看是哪一列。因为我们是按行拉的，所以行和列的分母永远是列数 n，而不是行数 m。

2.3 三种解法的横向对比

在面试里，这道题通常会出现三种解法。

第一种：两次二分。先用二分找到最后一行 matrix[i][0] <= target 的行，再在这一行内二分列。复杂度 O(log m + log n)。思路直观，但实现时要特别注意“定位行”的边界条件。比如 target 比第一行第一个还小，或者比最后一行最后一个还大，需要处理。

第二种：一次二分。直接把一维下标作为二分对象，每次通过映射取矩阵中的值。复杂度 O(log(m*n))。代码最简，面试时最推荐。

第三种：走右上角或左下角，每次排除一行或一列。复杂度 O(m+n)。这题也能做，但并不是最优。它更像是 240 题的专属解法。万一面试官问“你还有没有别的方法”，把这种解法拿出来当补充，会显得你储备够。

下面用表格做个对比，方便你写题解时直接用：

两种二分虽然复杂度看起来差不多，但一次二分的代码写起来更少，而且不容易因为“行定位”写错而漏判。我个人刷题的时候，遇到这种“整体有序”的二维矩阵，一律先想到拉直，而不是先想行和列。

3. 手写实现：一次二分的完整代码与边界条件清单

3.1 二分模板怎么选

二分查找的模板五花八门，我最推荐的是“左闭右闭”的写法，也就是 left 和 right 都指向有效范围，循环条件用 while (left <= right)。原因很简单：这个模板最不容易出现死循环，也最好理解。

标准模板如下：

• 初始化 left = 0, right = m * n - 1；
• mid = left + (right - left) / 2，不用 (left + right) / 2，是为了防止两个大整数相加溢出；
• 如果 matrix[mid / n][mid % n] == target，返回 true；
• 如果小于 target，说明目标在右侧，left = mid + 1；
• 如果大于 target，说明目标在左侧，right = mid - 1；
• 循环结束返回 false。

这里有一个非常容易被忽略的点：如果你用 while (left < right)，循环结束时 left 可能落在 right 右边，而且最后一个元素没有被比较。虽然你可以在循环外面补一句 matrix[left / n][left % n] == target 来兜底，但这样的代码可读性差，面试官还得额外确认。直接用 <= 版本，把退出循环的条件和“找不到”绑定在一起，逻辑更干净。

3.2 Python 和 Java 实现示例

先给一个 Python 版本，这段代码可以直接跑通过 LeetCode：

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m = len(matrix) if m == 0: return False n = len(matrix[0]) if n == 0: return False 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

再给一个 Java 版本，思路完全一致：

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

注意，Java 里的 int mid = left + (right - left) / 2 已经能防溢出。Python 由于整数不固定位数，直接 (left + right) // 2 也不会溢出，但写成 left + (right - left) // 2 更贴近面试中跨语言的标准写法。

3.3 边界条件与防坑清单

我见过太多人在这道题上栽跟头，问题基本都出在以下几个边界场景。

首先是空矩阵。matrix.length == 0 和 matrix[0].length == 0 要分开判断。特别是 matrix = [[]] 这种输入，m 不为 0，但 n 为 0，如果不判断 n == 0，后面 m*n = 0，索引计算时 matrix[mid // n] 会因为 n = 0 直接抛除零异常。

其次是单元素矩阵。比如 matrix = [[5]], target = 5，此时 left = right = 0，循环第一次就命中，返回 true。如果用 left < right 的模板，初始 left = 0, right = 0，循环不执行，就会返回 false，于是必须补后面判断，很容易漏。

再就是 target 比矩阵最小值还小，或比最大值还大。这其实不用特殊处理，因为二分会把区间逐渐缩小到空，然后返回 false。但很多人习惯在二分前先拿 matrix[0][0] 和 matrix[m-1][n-1] 做一次快速裁剪，我也这么做，理由是能让极端情况少走几次循环。不过要注意，裁剪本身也要判空，别让 matrix[m-1][n-1] 在空矩阵上越界。

还有一个细节：如果矩阵里存在重复元素，也就是“非严格递增”，这道题因为只判断存在性，所以依然适用。大家平时练的题目都是严格递增，所以很少有人提这一点，但实际面试扩展时可能会问。

写完代码建议直接把这五种用例在本地跑一遍。我在 LeetCode 上提交之前都会先在本地把这些边界跑通，虽然平台会给你判，但本地跑一遍能帮你把思维漏洞补齐。

4. 面试延伸：把这道题放进有序查找和动态规划的坐标里

4.1 与 240 题“搜索二维矩阵 II”对比

很多人刷完 74 题，紧接着会碰 240 题。这两道题名字很像，但解法差别很大。

240 题的条件是：每行从左到右递增，每列从上到下递增。注意，它没有“每行第一个数大于上一行最后一个数”，所以不能把整个矩阵当成一个一维有序数组。强行拉直可能会得到 [1,4,7,2,5,8,3,6,9] 这种乱序序列。

240 题的标准解法是从右上角出发：当前值大于 target 就左移一列，当前值小于 target 就下移一行。每一步都能排除一整行或一整列，所以最坏情况走 m+n 步。这个思路的本质是利用“行和列各自有序”制造局部单调性，而不是全局单调性。

我建议你在刷题时把这两题放到一起，用表格整理它们的数据条件差异：

这个表格如果是面经里的加分项，因为大多数候选人只会分别背两个题，很少有人能一句话说清“74 能二分，240 不能二分”的根本原因。你只要说出“拉直后是否整体有序”这句话，面试官基本就能确认你是真懂。

4.2 从二分查找延伸出去的三个常考变体

74 题只是二分的基础用法，面试更爱考的是“边界型”二分。最常见的有三类。

第一类是查找第一个等于 target 的元素。比如数组 [1,2,3,3,3,4]，要求返回 index=2。二分命中后不能直接返回，而是继续往左收缩 right = mid - 1。

第二类是查找最后一个等于 target 的元素。对称地，命中后继续往右收缩 left = mid + 1。

第三类是查找第一个大于等于 target 的元素，也就是常说的“插入位置”。这类题目和 C++ 的 lower_bound 函数对应。

74 题其实可以理解成“在虚拟的一维数组中查找等于 target 的元素是否存在”，它不要求返回位置，所以是三种变体里最简单的一种。先把这个练熟，再去啃那三个变体，梯度会舒服很多。

关于第一类，网上有个很形象的类比：你在一条排好队的队伍里找“第一个姓张的人”，找到任何一个姓张的都不算完，必须确认他前面不是姓张才停止。二分边界题的核心就是把“确认前面没有满足条件”这个过程用区间收缩来完成。

4.3 澄清一下热词里的“动态规划”

标题里带了“hot100动态规划”这个热词，我猜是搜索联想把“hot100”和“动态规划”关联到一起了。这里有必要说一句：74. 搜索二维矩阵不是动态规划题，它是二分查找/双指针类的题目。

动态规划用于解决“有重叠子问题”的决策类问题，比如矩阵路径计数、最小路径和、最长递增子序列。它们的二维矩阵往往没有全局有序性，而是通过状态转移方程自底向上推结果。

如果把查找类问题和 DP 类问题混在一起，面试时会被追问到很难堪。因为你一旦说“这题用动态规划”，面试官马上会问状态定义是什么、转移方程是什么、初始值是什么，而这题根本没有这些。

正确的分类方式是这样的：

• 有序二维结构里找目标 -> 二分或双指针；
• 二维矩阵里求最大/最小路径、计数、最长公共子序列 -> 动态规划；
• 二维矩阵里做连通性判断 -> DFS / BFS / 并查集。

刷 Hot 100 的时候，最好先给题目打标签。把 74 题放进“二分查找”文件夹，把“杨辉三角”“最小路径和”这类放进“动态规划”文件夹。标签分对了，复习的时候思路才不会乱。

5. 常见问题与排查实录：我实际踩过的坑

5.1 命名混乱导致的行列换算错误

我先说一个很低级但很容易犯的错：变量命名。很多人的代码里习惯用 m 表示行数、n 表示列数，但在换算时写成 matrix[mid / m][mid % m]。题目给的是 3 行 4 列，mid=7，如果你除以 3，得到的行号是 2，余数是 1；真实情况应该是第 7 / 4 = 1 行，第 7 % 4 = 3 列。结果完全不一样，但代码不一定会越界，因为 3 也是有效行数，而余数 1 可能是有效列，于是出现“搜得到但位置不对”的诡异错误。

这个错误最坑的地方在于：你很难一眼看出来，因为索引不会崩溃，只有部分 test case 会失败。我当时调试了很久，最后打印 mid、row、col 三者的对应关系才发现问题。从那以后，我写这类代码一定会先在注释里标注：

# m 是行数，n 是列数 # index = row * n + col # row = index // n, col = index % n

这行注释看起来废话，但能救人一命。

5.2 两次二分版本的坑

一次二分已经是最简写法了，但我还是见过不少同学非要用“先找行，再找列”的版本。如果你也想掌握这个版本，注意一个核心细节：找行时，while 条件建议用 left < right，并且 mid 偏向右侧，否则可能死循环。

举个例子，你要找“最后一行的行首元素小于等于 target”的那一行。考虑 matrix = [[1,3],[5,7]]，target = 6，你希望定位到第二行。如果你写的 mid = (left + right) // 2，当 left=0, right=1 时，mid 恒等于 0，matrix[mid][0] = 1 <= 6 成立，left 更新为 mid，于是 left 永远是 0，进入死循环。解决办法是把 mid 改成偏向右侧，写成 mid = (left + right + 1) // 2，这样 mid 会偏向右侧，区间才会收缩。

这类坑在标准模板里不会出现，但只要你想写更复杂的“边界二分”，就一定会碰到。所以我不建议新手在 74 题上写两次二分。先用一次二分把题过了，等以后在 34 题“在排序数组中查找元素的第一个和最后一个位置”里再专攻区间收缩技巧。

5.3 本地调试方法：把每一步打印出来

如果你搜到的结果不对，最快的定位方式就是打印二分过程。用一个临时脚本，在每次循环里输出 left、mid、right、matrix 对应值和 target：

matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] target = 16 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] print(f"left={left}, mid={mid}, right={right}, val={val}") if val == target: print("found") break elif val < target: left = mid + 1 else: right = mid - 1 else: print("not found")

我实际调试时发现，当 target=16 时，第一次 mid 会落在 index=5，也就是矩阵的 [1][1] 位置，值是 11。因为 11 < 16，所以 left 跳到 6，接着 mid 变成 6，访问 matrix[1][2] 是 16，命中。这个过程打印出来，你一眼就能理解“为什么一维下标 6 对应的是第二行第三列”。

调试完之后记得把这个临时脚本删掉，不要提交到平台。

5.4 空间复杂度和真实耗时验证

这道题空间复杂度是 O(1)，因为只用了几个变量。时间上，m*n 最大到 10^4 或 10^5 级别时，二分最多执行二十多次，这个性能无论如何都能过。

但有一种“假优化”需要避免：有人把二维矩阵先复制成一个一维数组，再对一维数组做二分。这会让空间复杂度变成 O(m*n)，而且复制本身也要时间，完全违反了题目考察的初衷。虽然能通过测试，但面试官问起时间空间复杂度你会很难解释。

正确的做法是“逻辑上认为是一维，物理上仍然访问 matrix[mid // n][mid % n]”。这就是所谓“以 O(1) 空间换虚拟索引”，也是这道题最值钱的地方。

6. 给刷题朋友的一个实在建议

如果你正准备开始刷 Hot 100，我个人建议别一上来就背 74 题的模板。先做一遍“从一维下标换算二维坐标”的推导，自己画一个 3x4 的矩阵，手动模拟 left、mid、right 的每一步变化。这个过程看起来慢，但它会帮你建立一种直觉：只要一个结构具备全局单调性，二分就能上；至于它是数组、是矩阵拉直、还是某些函数的返回值，这些都只是表现层。

等到你刷到后面，遇到“有序矩阵中第 K 小的元素”（LeetCode 378）、“寻找峰值”（162）这些题时，会回来感谢 74 题帮你打下的底子。我自己刷题的习惯是每道题只保留一份最简洁的题解，并在旁边标注“核心考点”和“易错点”，比如 74 题我会写“核心考点：全局单调性 + 坐标映射；易错点：分母用列数 n”。

最后再说一个小技巧：如果面试官不管你用什么方法，让你“快速判断矩阵里有没有这个数”，你可以先检查 target 是否小于 matrix[0][0] 或大于 matrix[m-1][n-1]，是就直接返回 false。这不是必需的优化，但会让你的代码多一层防御，也会让面试官觉得你考虑得周全。实测很多边界 case 因此直接跳过二分，代码表现更清爽。