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 100Hot 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(mn)。这题也能做但并不是最优。它更像是 240 题的专属解法。万一面试官问“你还有没有别的方法”把这种解法拿出来当补充会显得你储备够。下面用表格做个对比方便你写题解时直接用解法时间复杂度空间复杂度实现难度适用场景两次二分O(log m log n)O(1)中强调行内有序、跨行二分不方便时一次二分O(log(m*n))O(1)低本题最优解首推右上角移动法O(mn)O(1)低LeetCode 240 的典型解法本题可作扩展两种二分虽然复杂度看起来差不多但一次二分的代码写起来更少而且不容易因为“行定位”写错而漏判。我个人刷题的时候遇到这种“整体有序”的二维矩阵一律先想到拉直而不是先想行和列。3. 手写实现一次二分的完整代码与边界条件清单3.1 二分模板怎么选二分查找的模板五花八门我最推荐的是“左闭右闭”的写法也就是 left 和 right 都指向有效范围循环条件用 while (left right)。原因很简单这个模板最不容易出现死循环也最好理解。标准模板如下初始化 left 0, right m * n - 1mid 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 版本这段代码可以直接跑通过 LeetCodeclass 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] 在空矩阵上越界。还有一个细节如果矩阵里存在重复元素也就是“非严格递增”这道题因为只判断存在性所以依然适用。大家平时练的题目都是严格递增所以很少有人提这一点但实际面试扩展时可能会问。边界场景数据示例期望结果最容易犯的错空矩阵[] 或 [[]]false忘记判 n 0除零崩溃单元素命中[[5]], target5true用 left right 模板漏判单元素未命中[[5]], target3false坐标换算写反访问越界目标在行首[[1,3,5]], target1true二分正确但被行定位干扰目标在行尾[[1,3,5]], target5true退出循环前漏判最后一个写完代码建议直接把这五种用例在本地跑一遍。我在 LeetCode 上提交之前都会先在本地把这些边界跑通虽然平台会给你判但本地跑一遍能帮你把思维漏洞补齐。4. 面试延伸把这道题放进有序查找和动态规划的坐标里4.1 与 240 题“搜索二维矩阵 II”对比很多人刷完 74 题紧接着会碰 240 题。这两道题名字很像但解法差别很大。240 题的条件是每行从左到右递增每列从上到下递增。注意它没有“每行第一个数大于上一行最后一个数”所以不能把整个矩阵当成一个一维有序数组。强行拉直可能会得到 [1,4,7,2,5,8,3,6,9] 这种乱序序列。240 题的标准解法是从右上角出发当前值大于 target 就左移一列当前值小于 target 就下移一行。每一步都能排除一整行或一整列所以最坏情况走 mn 步。这个思路的本质是利用“行和列各自有序”制造局部单调性而不是全局单调性。我建议你在刷题时把这两题放到一起用表格整理它们的数据条件差异对比项74 题240 题行内递增是是列内递增是是行首 上一行行尾是否能否按行拉直能不能最优解法一次二分 O(log(m*n))右上角移动 O(mn)这个表格如果是面经里的加分项因为大多数候选人只会分别背两个题很少有人能一句话说清“74 能二分240 不能二分”的根本原因。你只要说出“拉直后是否整体有序”这句话面试官基本就能确认你是真懂。4.2 从二分查找延伸出去的三个常考变体74 题只是二分的基础用法面试更爱考的是“边界型”二分。最常见的有三类。第一类是查找第一个等于 target 的元素。比如数组 [1,2,3,3,3,4]要求返回 index2。二分命中后不能直接返回而是继续往左收缩 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 列mid7如果你除以 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当 left0, right1 时mid 恒等于 0matrix[mid][0] 1 6 成立left 更新为 mid于是 left 永远是 0进入死循环。解决办法是把 mid 改成偏向右侧写成 mid (left right 1) // 2这样 mid 会偏向右侧区间才会收缩。这类坑在标准模板里不会出现但只要你想写更复杂的“边界二分”就一定会碰到。所以我不建议新手在 74 题上写两次二分。先用一次二分把题过了等以后在 34 题“在排序数组中查找元素的第一个和最后一个位置”里再专攻区间收缩技巧。5.3 本地调试方法把每一步打印出来如果你搜到的结果不对最快的定位方式就是打印二分过程。用一个临时脚本在每次循环里输出 left、mid、right、matrix 对应值和 targetmatrix [[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(fleft{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)我实际调试时发现当 target16 时第一次 mid 会落在 index5也就是矩阵的 [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 因此直接跳过二分代码表现更清爽。
