搜索二维矩阵这道题在力扣Hot100里属于那种“看着简单、写着翻车”的典型。我第一次刷它的时候也觉得不就是个二分吗结果在边界条件上卡了半小时后来面试又被同样的考点追问过一次才算彻底把这个题吃透。今天把这题的完整思路、两种主流写法、还有我在实际刷题和面试中踩过的坑一次性摊开讲清楚。如果你正在备战面试、刷力扣热题100或者在学二分查找但总是搞不清边界这篇文章值得你花十分钟认真看完。它不是简单给你贴一份能跑的代码而是把“为什么这么做”讲透让你下次遇到变种题也能举一反三。1. 题目拆解与核心思路1.1 原题到底在说什么先看题目描述。你有一个m x n的矩阵这个矩阵有两个性质每行从左到右是递增的每行的第一个整数大于前一行的最后一个整数目标给定一个target判断它是否存在于矩阵中。举个例子一个典型的输入长这样1 3 5 7 10 11 16 20 23 30 34 60target 3返回 truetarget 13返回 false。注意第二个性质很关键。它意味着这个矩阵不仅仅是每一行内部有序而是整个矩阵从上到下、从左到右按行展开后是一个全局递增的一维数组。这是这道题能用“一次二分”做出来的根本前提。如果只满足每行递增、不满足“行间也递增”那道题就变成了力扣240题搜索二维矩阵II解法思路完全不一样这个后面我会专门提一嘴防止你搞混。1.2 两种看待矩阵的视角这道题的核心难点其实不是二分本身而是你如何看待这个矩阵。视角一把二维矩阵“拍扁”成一维数组。因为矩阵满足全局递增所以你可以想象把它按行拆开、首尾相接变成一个长度m*n的有序数组。有序数组里二分查找这是任何学过算法的人都会的。剩下的问题无非是怎么在一维下标和二维坐标之间互相换算。视角二把这个矩阵看成一棵二叉搜索树。怎么看成树你把矩阵的右上角或者左下角当作根节点然后会发现一个非常漂亮的规律往左走值变小往下走值变大这不就是一棵二叉搜索树吗而且每次移动都能排除掉一行或一列复杂度是O(mn)。这个视角后面展开讲它是一个很漂亮的解法不过如果追求最优复杂度还得看二分。1.3 这题为什么值得刷我自己的判断标准是一道题值不值得反复刷看三点——考点是否高频、思路是否通用、坑是否典型。这题三个全占。二分查找本身就是面试必考而这题又是二分在二维场景下的变体。很多公司喜欢在二分基础上加一点“包装”二维矩阵就是这个包装。你要是只刷过纯一维的二分遇到这题很容易懵但如果你刷过这题反过来对一维二分的理解也会更深。另外这题在力扣上被归为Hot100即热题100本身就说明它的出题频率和代表性强。很多人刷题喜欢追求数量我不太认同。把这种高频基础题吃透比刷十道边角料题有用得多。2. 核心解法一把矩阵当一维数组做二分2.1 核心思路与下标换算第一种解法也是我认为最优的解法就是把这个m x n的矩阵想象成一个长度为m*n的有序数组然后做标准的二分查找。一维数组的第mid个元素对应到矩阵里就是行号row mid / n整除列号col mid % n取余这个换算要理解不要死记。你可以这么想一维下标从0开始每满n个元素换一行所以除一下得到行号余一下得到列号。反过来也成立row * n col就是一维下标。取n而不是m是因为每行有n列一行走完才换下一行。这个解法的时间复杂度是O(log(m*n))空间复杂度O(1)。它是所有解法里最优的也是面试时最推荐主动给出的方案。2.2 边界与循环不变量二分的核心是循环不变量。我刷了这么多题最深的体会是如果你写二分总出错一定是没在动手前想清楚“我的搜索区间到底是什么、每次循环后区间怎么收缩”。这题里我维护的循环不变量是left指向的可能是target的区间左边界right指向的可能是target的区间右边界循环条件left right意味着当前搜索区间[left, right]非空每次取mid left (right - left) / 2拿matrix[mid / n][mid % n]和 target 比相等找到了返回 true小于 target说明target在右半边left mid 1大于 target说明target在左半边right mid - 1循环结束说明区间空了返回 false。这里有个细节mid left (right - left) / 2和mid (left right) / 2等价但前者在left right特别大时能避免整数溢出。刷题时数据范围不大可能溢出但我建议养成这个习惯如果你后面刷到涉及大数的二分题这个习惯能帮你少踩一次坑。2.3 完整参考代码我用Java写了一份可以直接跑的版本class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; int n matrix[0].length; int left 0; int right m * n - 1; while (left right) { int mid left (right - left) / 2; int midValue matrix[mid / n][mid % n]; if (midValue target) { return true; } else if (midValue target) { left mid 1; } else { right mid - 1; } } return false; } }代码本身不长但它把前面说的所有要点都浓缩进去了。空矩阵检查、下标换算、区间收缩一步都不能少。我见过有人把right初始化为m * n循环条件写成left right这也能跑通但属于另一种写法风格。我建议新手先认准一种写透不要今天用闭区间明天用开区间换来换去最容易出bug。2.4 一次二分和两次二分怎么选这题还有另一种二分思路先在列上二分找到目标行再在行上二分找到目标值。我不推荐这个写法原因有三个第一次二分找“最后一个小于等于target的行”这个操作边界处理比直观看起来麻烦很容易写成死循环或漏边界。二次二分相加的时间复杂度还是O(log(m) log(n))本质上等于O(log(m*n))并没有比一次二分更优。一次二分的代码更短、逻辑更干净、面试时更容易讲清楚复盘成本低。如果你在面试我建议直接用“一次二分 下标换算”这个方案。它是最优的而且讲起来一气呵成面试官很难在这个点上继续刁难你。3. 解法二把矩阵看成二叉搜索树3.1 为什么从右上角开始第二种思路完全不碰二分但我个人非常喜欢因为它很巧妙地揭示了矩阵结构本身的信息。你看矩阵的右上角那个元素它是它所在行的最大值同时也是它所在列的最小值。这个位置极其特殊它同时拥有行和列两边的“有序信息”。从右上角(0, n-1)出发比较当前值和 target如果当前值等于 target找到了如果当前值大于 target因为当前值是这一行的最大值target不可能在这一行所以列坐标左移一列如果当前值小于 target因为当前值是这一列的最小值target不可能在这一列所以行坐标下移一行每次移动都排除了整整一行或一整列。这样最多走m n步时间复杂度O(m n)。对称地从左下角出发也行规律是“大于就右移一列小于就上移一行”。原理一样建议你只记其中一个方向最好记右上限。3.2 完整参考代码class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; int n matrix[0].length; int row 0; int col n - 1; while (row m col 0) { int cur matrix[row][col]; if (cur target) { return true; } else if (cur target) { col--; } else { row; } } return false; } }这个写法还有一个额外的好处它是力扣240题无序矩阵标准解法的一个特例。240题的矩阵只保证每行递增、每列递增不保证“行间也递增”所以不能拍扁做二分但依然能用这个“右上角出发”的方法。所以说如果你先学了这个解法再去碰240题会非常顺畅。一道题打通两题的路子性价比很高。3.3 两种解法怎么取舍如果你追求最优复杂度选解法一O(log(m*n))稳赢。如果你是面试想展示思维层次或者担心自己在紧张状态下写错二分边界解法二更稳O(mn)虽然不如二分理论最优但胜在逻辑简单、代码短、不容易出错。实际面试中我更推荐你先提解法一并写出来然后补充说“其实这里还有一种二叉搜索树视角”顺手把解法二也讲出来。这会给面试官留下“这个人思路开阔”的印象。讲的时候注意别只背代码要把“右上角是行的最大值、列的最小值”这个判断逻辑讲清楚这才是考察点。4. 实操中的常见坑与排查思路4.1 空数组与单行单列的边界这题最隐蔽的坑之一出现在这类测试用例上matrix [[]] matrix [[1, 3, 5]] matrix [[1], [3], [5]]matrix[0].length 0这种空矩阵最容易漏判。我的习惯是写一个组合条件一次性把matrix null、matrix.length 0、matrix[0].length 0全部拦掉。别分开写合在一起既省代码又避免中间忘记返回。单行矩阵其实很考验你的一维下标换算有没有理解。n 1时mid / 1 midmid % 1 0相当于每一行只有一个元素你其实是在对第一列做二分这个逻辑在代码里自然成立不用特殊处理。4.2 求中位数的溢出陷阱(left right) / 2这个写法在left和right都是大数时理论上存在加法溢出导致的负数问题会直接让程序崩溃。虽然力扣的数据范围一般够不到这个量级但我坚持在每道二分题里都用left (right - left) / 2的写法。一是养成习惯二是如果面试官追问“你的mid写法有什么讲究”你可以顺势展示自己对细节的把控。顺带说一句还有个left ((right - left) 1)的位运算写法也常见效果一样但可读性差一些。刷题求快可以用写在正式项目里还是算了吧。4.3 下标换算的快速自检法我当年学这个换算的时候总是担心取错n还是m。后来我找到一个非常快的自检方法想象一个3 x 4的矩阵一维下标0, 1, 2, 3应该对应第一行下标4, 5, 6, 7对应第二行。取mid 5验证5 / 4 1第二行5 % 4 1第二列没错。取mid 3验证3 / 4 0第一行3 % 4 3第四列也没错。你只要在脑子里过一遍这个例子就知道除数必须是列数n。犯一次错记住教训下次直接就能反应过来。4.4 从错误用例中提炼经验我整理一下这题最容易踩的几个用例方便你自测时快速覆盖输入矩阵target预期输出考察点[[]]1false空矩阵检查[[1,3,5,7]]5true单行、常规查找[[1],[3],[5]]4false单列、区间收缩[[1,3,5,7],[10,11,16,20],[23,30,34,60]]3true标准多行情况[[1,3,5,7],[10,11,16,20],[23,30,34,60]]13false值在行间空洞中[[1,3]]1true行首最小元素尤其注意target 13那个用例它位于第一行和第二行之间的“数值空洞”里。这个用例能测出你的二分收缩逻辑是否真正理解而不是碰巧跑对。5. 从面试延伸出去的点5.1 面试官的追问套路这题如果在面试中出现最常见的追问大致有这么几类如果矩阵不满足“行间也递增”只保证每行递增、每列递增怎么做对应力扣240题回到右上角法你用的二分是闭区间写法换成半开区间怎么写考察你对循环不变量是否真的理解如果要频繁查询多个target怎么优化预处理或构建索引考察的是工程思维如果矩阵很大、内存装不下怎么办外排序、数据分片考察的是系统设计思维我自己面试别人的时候也喜欢问这类题。说实话写对二分的人不少能说清“为什么循环条件要这样写”“为什么收缩边界要加减一”的人比例低很多。面试官真正考察的点其实是后者。5.2 和力扣240题的对比与边界你还得知道什么时候不能当一维数组做二分。240题的矩阵只保证每行从左到右递增每列从上到下递增这种矩阵不满足“行间也递增”所以你没法拍扁做二分。但是右上角出发的解法依然成立因为“右上角是行的最大值、列的最小值”这个性质没有被破坏。我建议你把74题和240题放在一起刷对比一次胜过一个暑假闷头刷一百道不相关的题。这两道题放在一起恰好覆盖了矩阵搜索的两种核心模型理解了它们的区别面试里再出现各种“有序矩阵”变体你心里就有底了。5.3 这题在日常开发中的投影有人可能会想算法题刷了是不是面试完就忘了我自己的经验是里面的思想会沉淀下来。一次二分里“二维坐标和一维下标互相映射”的思路在处理分页、格子地图、数组扁平化等场景时都会反复用到。右上角出发的“每步整行整列排除”的思路本质上是一种贪心的排除法你做数据筛选、剪枝的时候也会有类似的直觉。刷题不能只背答案要把题目背后那道“思维肌肉”练出来。这题强度刚好不算难到劝退又够深到值得反复琢磨所以我挺推荐把它作为Hot100刷题的第一梯队来对待。6. 刷题心态与复盘建议6.1 一道题刷到什么程度算“会了”我的标准很简单不看题解能独立写出AC代码不看代码能用自己的话把思路讲清楚能回应面试官关于边界条件和复杂度分析的追问。三个条件全满足才算过关。如果刷了三遍还会在某个细节卡壳别急着怪自己笨。二分的边界条件本来就反直觉大部分人都不是一次就会的。我第一次写这题的时候就在right m * n - 1还是right m * n上犹豫了半天后来干脆固定一套写法不再来回改问题自然就消失了。6.2 建议的刷题顺序搭配如果你正在按Hot100顺序刷题我比较推荐的搭配是这样的先刷一道标准的二分查找题找感觉然后刷这题紧接着刷240题做对比。三题连着刷基本就能把“有序数组/有序矩阵搜索”这个套路焊在脑子里了。如果你想追加变体还可以看看“搜索旋转排序数组”那一类题那又是二分查找的另一个分支侧重点在“部分有序”和这题恰好形成互补。6.3 我给你留的几道小题如果你看完这篇想自测一下掌握程度可以不急着往下刷先想这三个问题为什么解法二从右上角出发能保证每次移动都是安全的不会漏掉target一次二分的解法为什么不需要先定位到某一行如果给你一个无限大的有序矩阵要求设计一个查找方案你会怎么做能答出前两个这题的通关进度大约在一半以上能答出第三个说明你已经能把这题的知识迁移到新场景里了。那才是刷题真正的收获。我个人在实际刷这题的时候最大的体会就是别嫌题简单简单题里藏的门道最值得抠。它有最优解的空间有不同视角的解法有边界条件的陷阱还有一整类变体题的入口这种信息密度对刷题来说很难得。把它钉死了Hot100后续遇到的许多二分和搜索题都会轻松不少。
