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(mn)。面试的时候我习惯先从暴力解法讲起再逐步优化到二分。这样面试官能看到你完整的思考链路而不是背答案。接下来把这几种解法挨个拆开每种的思路、代码、坑都讲一遍。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 三种解法对比与选型建议解法时间复杂度空间复杂度代码量风险点暴力遍历O(mn)O(1)很少大矩阵会超时两次二分O(log m log n)O(1)中等第一次二分的边界模板容易错一次二分O(log(mn))O(1)最少坐标映射容易错注意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 列的矩阵把一维索引标上再自己推一遍 mid5、mid7、mid11 分别对应哪个元素。这个习惯能帮你避免大部分低级错误。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 版本需要注意vectorvectorint的引用传递避免拷贝整个矩阵。另外m * n可能会溢出如果 m 和 n 都是 int 类型在某些极端情况下相乘可能超过 INT_MAX所以可以改成long long total (long long)m * n或者直接用left和right分别记录行列的乘积。bool searchMatrix(vectorvectorint 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 位于较上面的行时假设top0, bottom1算出mid (01) // 2 0如果matrix[0][0] target那么top mid 0top 没有前进下一次循环还是top0, bottom1陷入死循环。排查方法很简单在循环里打印top、bottom、mid的值看到三者不再变化就说明 mid 的计算方式有问题。解决办法是把 mid 改成向上取整mid (top bottom 1) // 2这样当top0, bottom1时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(mn)。面试里如果被问到“能不能再快一点”答案是不能因为如果矩阵只有行列有序理论上需要至少 O(mn) 才能找到或排除。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 一个问题带出整片知识网最后说点我自己的刷题体会。搜索二维矩阵这道题我前前后后刷了不下五遍。不是因为我记性差而是每次隔一段时间重刷都会发现自己对二分检索、边界处理、坐标转换的理解又深了一点。第一遍刷我只会暴力法第二遍学会了两次二分第三遍能写一次二分但坐标转换偶尔写错第四遍终于把边界条件和溢出问题彻底吃透第五遍开始主动归纳旋转数组、找峰值、找边界这些衍生题。这个过程对我自己的成长帮助很大。所以如果你现在觉得题目难别急把它放进收藏夹隔一个月再写一遍感受完全不一样。