这题我第一次刷是在准备一次线上笔试的时候当时看到“二维矩阵”四个字下意识就想上双层循环暴力查找。结果编译都通过了我心里也清楚这题放进 hot100肯定不是为了让你用 O(m*n) 的遍历混过去。搜索二维矩阵力扣hot100第67题也就是大家熟悉的那道题真正想考的是你能不能从一个严格有序的二维结构里读出“一维有序”的本质。题目只给了两个条件——每行从左到右升序并且每行的第一个整数大于上一行的最后一个整数。翻译成人话就是整个矩阵按行拼接起来就是一个不折不扣的有序数组。既然有序二分查找就是首选方案最优时间复杂度能压到 O(log(m*n))。这篇文章我会把三种思路完整过一遍一次二分、两次二分、还有右上角开始的 Z 字搜索。重点讲索引映射和边界处理这两块是我自己踩过坑之后重新总结出来的直接照着用能少走不少弯路。适合正在刷 hot100 的朋友也适合面试前想彻底吃透二分边界的人。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(m*n)。如果矩阵规模只有 100×100数据量一万确实也能跑完。可一旦 m 和 n 都到 10^5 级别暴力就是 10^10 次比较基本等于报废。力扣这道题的意图也很明显给了一个强有序的结构就是为了让你把搜索空间砍半又砍半。用一次二分的复杂度是 O(log(m*n))拿 10^6 个元素来说也就是大概 20 次比较。这个差距在数据规模增大后会指数级放大所以暴力在工程环境里基本没有讨论价值。还有一点我想提醒不要觉得“反正力扣数据小暴力能过就行”。面试官看到你用双层循环解这道题第一反应是你没有观察到矩阵整体有序这个关键性质这一题的核心分就丢了。做题的目的是训练思路不是为了过用例。2. 一次二分把二维数组“拉直”的魔法2.1 一维下标到二维坐标的映射关系一次二分的核心就一句话把二维矩阵当成一个长度为 m*n 的一维有序数组来搜然后用数学公式把一维下标换算成二维坐标。假设矩阵有 m 行 n 列某个元素在一维数组中的下标是 idx那么它对应的行和列分别是行号row idx // n列号col idx % n这里的 n 是列数不是行数很多人第一次都会搞反。为什么列数是 n因为按行优先存储时每走完一整行下标会跳过 n 个元素。拿 3 行 4 列的矩阵举例一维下标 4 对应的是第二行第一列因为 4 // 4 14 % 4 0。如果错误地写成idx // m得到的是 4 // 3 1看起来可能还碰巧对但换一个下标就露馅了。实际计算时下标 5 对应5 // 4 15 % 4 1正确结果是 matrix[1][1]第二行第二列也就是 11。如果错用行数做除数5 // 3 15 % 3 2就变成 matrix[1][2]第二行第三列指向了 16直接错位。这个映射关系是整个解法的地基。你只要写对一次后面的二分逻辑就跟一维数组一模一样。2.2 完整实现与复杂度分析我习惯用“左闭右闭”模板也就是left right这种写法因为它的循环终止条件最直观不容易漏掉元素。每次取中点时用mid left (right - left) // 2避免两个大数相加溢出。Python 实现如下def searchMatrix(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 mid_val matrix[mid // n][mid % n] if mid_val target: return True elif mid_val target: left mid 1 else: right mid - 1 return False整个过程不再区分行和列left 和 right 表示的是一维区间。mid 换算成二维坐标后取到的中间值跟 target 比较然后正常收缩区间。复杂度方面时间复杂度O(log(m*n))每次循环排除一半元素。空间复杂度O(1)只有几个临时变量。相比暴力遍历 O(m*n)这个提升是巨大的。假如矩阵有 1000 行 1000 列二分最多比较约 20 次就能出结果。2.3 为什么二分模板要选左闭右闭网上关于二分模板的争论很多什么“左闭右开”“左开右闭”“左闭右闭”各有一套说法。我个人的建议是选一种你最顺手的模板把边界条件彻底吃透不要每次都换。我选左闭右闭的原因是它逻辑最对称初始时 left 指向区间左端点right 指向区间右端点当 left 和 right 交叉也就是left right时说明区间为空搜索结束。中间值 mid 如果小于 target说明 target 只可能在 mid 右侧所以left mid 1如果大于 target说明 target 只可能在左侧所以right mid - 1。这种收缩方式每一步都不会把 mid 重复纳入区间避免了下标卡住不动造成的死循环问题。如果换用left right的写法循环退出时需要额外判断 left 位置的元素是否为 target因为退出时可能还有一个元素没比过。不是不行但多一层分支写题时容易忘。刷题阶段求稳我推荐left right。3. 两次二分先确定行再确定列3.1 第一次二分定位候选行一次二分固然简洁但有些面试官会沿着“二维”这个信息继续追问希望你展示对矩阵结构的进一步理解这时候两次二分就是一个很好的扩展思路。两次二分的做法是先在竖直方向上搜索确定 target 可能落在哪一行然后在该行内继续二分。定位行的逻辑是看每一行的第一个元素matrix[i][0]因为行内递增且行间递增所以行首元素组成的数组也是严格递增的。我们在这个数组里做二分找到最后一个满足matrix[i][0] target的行。只有在这一行里target 才有可能出现。为什么要“最后一个”因为如果 target 等于某个行首元素就找到了如果大于某个行首元素它必须往后面的行找。当 target 比所有行首都大时候选行就是最后一行当 target 比第一行的行首还小时说明整个矩阵都不可能有 target直接返回 False。第一次二分的代码片段left, right 0, m - 1 while left right: mid left (right - left) // 2 if matrix[mid][0] target: left mid 1 else: right mid - 1 row right循环结束后right 指向的就是最后一个满足条件的行。如果 right 小于 0说明没有任何行的行首小于等于 target可以直接 false。3.2 第二次二分在候选行内精确查找拿到候选行 row 之后问题退化成“在一个有序一维数组中搜索 target”这是最基础的二分场景left, right 0, n - 1 while left right: mid left (right - left) // 2 if matrix[row][mid] target: return True elif matrix[row][mid] target: left mid 1 else: right mid - 1 return False把两次二分合起来def searchMatrix(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 - 1 while left right: mid left (right - left) // 2 if matrix[mid][0] target: left mid 1 else: right mid - 1 if right 0: return False row right left, right 0, n - 1 while left right: mid left (right - left) // 2 if matrix[row][mid] target: return True elif matrix[row][mid] target: left mid 1 else: right mid - 1 return False3.3 一次二分 vs 两次二分怎么选两者复杂度很接近一次二分是 O(log(mn))两次二分是 O(log m log n)。在 m 和 n 比较均衡时log(mn) 等于 log m log n几乎没有差别。代码上一次二分更简洁但索引映射稍微需要理解一下两次二分更贴合“二维”的直觉边界判断也更直白。我刷题时会优先写一次二分因为它代码量最少出错概率低。如果面试官要求展示对二维结构的拆解能力或者故意引导你从行列两个维度思考我就切换到两次二分来讲。两种解法最好都练熟实际上它们用的是同一套二分思想只是切割方式不同。4. 高频踩坑点与调试记录4.1 空矩阵与空行最容易漏的边界我第一次提交就挂在空矩阵上报错信息是IndexError: list index out of range。原因很简单matrix 是[]时matrix[0]就已经越界了。处理方式是在最开始统一拦截if not matrix or not matrix[0]: return False注意这两个条件都要写。not matrix处理的是空列表not matrix[0]处理的是[[]]这种情况也就是有一行但没有任何列。这两个条件合起来能挡住所有二维矩阵为空的情况。这类边界判断看起来不起眼但在面试中是最容易被追问的地方。写代码时故意留一处空矩阵用例跑一遍确认返回 False能省不少调试时间。4.2 mid // n 还是 mid // mm 和 n 的位置别搞混这个坑我踩过而且是在本地跑测试用例跑了好几次才反应过来。很多人写一次二分时下意识把行数和列数搞混写成mid_val matrix[mid // m][mid % m]这行代码在 m 恰好小于等于 n 的某些用例上可能不会立刻暴露问题但只要矩阵不是正方形索引大概率越界。想清楚一个点就够了一维下标在矩阵中是按“行优先”方式分布的每向右移动 n 个位置就会跳到下一行。所以除数和取模的基数都必须是 n也就是列数。如果矩阵是 3 行 4 列一维下标 5 表示第 1 行第 1 列换算成5 // 4 15 % 4 1正好落在 matrix[1][1] 上。写成mid // m就全乱了。4.3 死循环与索引越界二分模板的稳定性二分最怕的就是死循环。最常见的原因是循环条件写错比如while left right时区间收缩逻辑没配对导致 left 和 right 始终差 1无法退出。用while left right配合left mid 1和right mid - 1每次 mid 至少有一个方向会收缩循环一定能退出。我在刷题时还习惯在代码里临时打印left、right、mid三者的值看它们的变化是否符合预期。打印几个用例之后你对区间收缩的理解会很扎实。还有一点计算 mid 时别写成(left right) // 2虽然力扣数据的数值规模通常不会溢出但在工程环境里 left 和 right 都可能很大left right可能超过整数上限。写left (right - left) // 2是更稳妥的做法这是一个值得养成的好习惯。4.4 负数和单一元素场景也要测很多人只测正数用例忽略了全负数矩阵。比如[[-10, -8, -6], [-5, -3, -1]]target -7正确的二分应该能返回 False。二分本身不关心元素正负它只关心序列是否有序全负数依然有序所以算法没问题但如果你在“边界判断”里用了matrix[mid][0] 0这种业务逻辑就会无端出错。单一元素矩阵比如[[5]]也值得单独测。此时 m 1, n 1一维区间长度是 1mid 0matrix[0 // 1][0 % 1]就是 matrix[0][0]直接命中。这个边界用例能帮你验证索引映射公式在最小规模下是否正确。5. 常见错误速查与复盘经验5.1 错误表现、原因与修正对照表我把实际调试中见过的错误整理成一张表刷题时对照着看会很有帮助。错误表现根本原因修正方式报错 IndexError: list index out of range空矩阵或空行没有拦截开头加if not matrix or not matrix[0]索引越界且数值错位一次二分中用 m 代替 n 做除法和取模用列数 n 计算mid // n和mid % n死循环程序卡住循环条件与收缩逻辑不匹配统一使用left right并分别做mid ± 1边界元素找不全循环退出时最后一个元素没被比较使用左闭右闭模板或在left right模板中补最后一次判断结果错误但逻辑看似没问题目标值小于所有行首候选行定位出错定位行后检查row 0的情况返回 False 但目标值确实存在二分区间初始化错了比如 right 写成 n - 1 而不是 m * n - 1一次二分的 right 初始化为m * n - 1这张表前面四行是我自己踩过的后面两行是帮别人看代码时发现的都属于这个题最容易碰到的典型毛病。5.2 我自己的一套写题复盘流程做完一道题后我不会立刻去看题解了事。虽然这题不算难但我还是会强制自己走一遍复盘流程这样比直接背答案有效得多。流程是第一重新口述一遍题目的关键条件确认自己真的理解矩阵整体有序的含义第二不看代码在纸上写出一次二分的索引映射公式第三手动跑两个测试用例一个存在 target一个不存在 target模拟 left 和 right 的每一步变化第四思考如果去掉“每行第一个整数大于上一行最后一个整数”这个条件解法该怎么变。第四步会逼迫你把一次二分的适用范围想清楚而不是只会套模板。这套流程看起来简单但坚持下来之后二分相关的题目我基本不会在边界上卡壳。建议你也试试最难的那一步——变式思考它往往能暴露你是否真正掌握了问题的本质。6. 延伸思考如果矩阵不是严格递增怎么办6.1 行内升序但行间不递增的情况一个很自然的问题如果去掉“每行的第一个整数大于上一行最后一个整数”这个条件只保留“每行从左到右升序每列从上到下升序”一次二分还能用吗答案是不能。原因很直接矩阵按行展开后不再是一个严格递增的序列整体不有序一维二分的应用前提就被破坏了。比如下面这个矩阵[[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16]]按行展开是1, 4, 7, 11, 2, 5, 8, 12, 3, 6, 9, 16中间出现了下降的部分所以整体二分不成立。力扣有一道高层级题就是这个设定要求在这种矩阵中搜索目标值这是对本题的重要变体。题目条件的每一条变化都可能改变算法选型。看到“每行第一个整数大于上一行最后一个整数”你要本能地想到整体有序看到“每列从上到下升序”那只是局部有序不能用同一种二分方式处理。6.2 右上角 Z 字搜索O(mn) 的替代方案当矩阵只是“每行每列各自升序”时有一个非常优雅的方案从右上角开始走。初始化在右上角也就是row 0, col n - 1然后重复下面的逻辑当前值等于 target直接返回 True当前值大于 target说明这一整列从当前位置往下都比 target 大所以列指针左移col - 1当前值小于 target说明这一整行从当前位置往左都比 target 小所以行指针下移row 1。实现如下def searchMatrix(matrix: list[list[int]], target: int) - bool: 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这个思路的复杂度是 O(mn)因为每次迭代要么行加一要么列减一总共最多移动 mn 步。它比暴力的 O(mn) 好得多但对于严格递增矩阵依然不如二分 O(log(mn))。但从右上角搜索这个思路很重要因为它不依赖“行间递增”这个强条件应用范围更广。面试时如果你能先给出一次二分再补充这个变式解法展示的是你对不同有序结构的理解深度。6.3 与 hot100 中其它矩阵搜索题的关联这道题跟“旋转排序数组”系列的思想有相通之处它们都是在一个“部分有序”或“整体有序”的结构上做搜索关键都在于利用题目给出的有序性质把搜索区间缩小一半。如果这道题你练熟了后面的“搜索旋转排序数组”“寻找旋转排序数组中的最小值”就会容易很多因为它们共享同一种分析思路先判断 mid 落在哪个有序区间再决定往哪边收缩。hot100 里的题目不是孤立的很多都是一脉相承的思路变体。我个人在实际操作中的体会是算法题最值钱的不是 AC 那一下的快感而是把边界条件想透之后再遇到同类题目时那种“一切尽在掌握”的感觉。这道搜索二维矩阵看起来简单但它在二分专题里起到的是承上启下的作用。你可以把“一次二分”和“两次二分”看作对同一性质的两层理解把“右上角 Z 字搜索”看作对强条件削弱后的备份方案。三种思路都过一遍这道题的收获就远超题目本身了。最后再分享一个小技巧做完这道题建议顺手把 LeetCode 上那道严格的“搜索矩阵”变体做一做然后对比两种解法为什么一个能用二分、一个只能走 Z 字搜索。这种对比比单纯刷十道相似题都要管用它能帮你把“有序结构决定算法结构”这件事真正刻进脑子里。