今天是我们刷题系列的第22天题目是 LeetCode 74搜索二维矩阵用 JavaScript 实现。这道题是二分查找题型里的常客在面试中出现频率不低核心考法就一个——在一个特殊有序的二维矩阵中高效查找目标值。题目本身不长但信息量很大。它的两条特性非常关键每行从左到右升序且每行第一个整数大于上一行的最后一个整数。这意味着整个矩阵可以被“摊平”成一个有序数组二分查找顺势登场。我当年第一次做这题时第一反应就是两层循环暴力遍历后来才慢慢理解二维坐标映射的美妙之处。今天这一篇我会把多种解法、最优解的完整推导、边界条件处理、易错点一次性讲透希望帮你把这道题彻底吃透。1. 题目概述与核心特性解读1.1 题目说的到底是什么LeetCode 74 的题目描述很简洁给定一个 m x n 的矩阵 matrix 和一个目标值 target判断矩阵中是否存在 target。矩阵满足两条硬性规定每行的元素从左到右升序排列每一行的第一个整数大于前一行的最后一个整数。注意第二条性质它是很多新手容易忽略的。行内升序其实很普通很多题目里矩阵行内都是有序的但“每行的第一个整数大于前一行的最后一个整数”才是这道题真正的题眼。它保证了行和行之间在数值上也是严格递增的不会出现区间重叠。举个例子const matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ];这里第二行第一个元素 10 大于第一行最后一个元素 7。也就是说整个矩阵按行读下来1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60是一个严格递增的一维序列。把矩阵“拉直”之后它和普通的一维有序数组没有任何区别。1.2 两条性质到底意味着什么如果矩阵真的有这种性质那我们就不必把它当成“二维”来对待了。我们可以把这个矩阵看成是一个长度为 rows * columns 的有序数组只是数据恰好按照每 columns 个一组被“切开”放到了不同的行里。这很像电影院的座位编号第一排 1 到 7 号第二排 8 到 14 号第三排 15 到 21 号。有人问你“18 号座位在第几排第几座”你不会从 1 号一路数到 18 号而是先判断 18 在哪个区间再算它在区间内的偏移量。LeetCode 74 考的就是这个场景。这个性质直接带来一个重要结论能用二分查找。在一维有序数组里二分查找的时间复杂度是 O(log N)在这里 N rows * columns也就是 O(log(mn))。这比 O(mn) 的暴力遍历高了一个级别也是面试官最想看到的思路。这道题适合谁来刷如果你的二分查找基础还不扎实或者对二维坐标映射不太敏感建议认真走一遍完整推导如果你已经会了也可以当作复习重点看后面第 4 章和第 5 章的边界细节我保证有收获。2. 三种解法对比与思路推导2.1 解法一暴力遍历能过但拿不到分最直接的思路是两层循环var searchMatrix function(matrix, target) { for (let i 0; i matrix.length; i) { for (let j 0; j matrix[0].length; j) { if (matrix[i][j] target) return true; } } return false; };这个解法能不能用在 LeetCode 的约束下还真能用m 和 n 最大也就 100总共 10000 次比较运行起来毫无压力。但面试如果只写这个基本等于告诉面试官你没有抓住题目的有序性。暴力解法没有利用任何矩阵性质属于“会遍历就能写”的回答。刷题的意义在于建立“数据有序就能加速”的思维而不是每次都用遍历兜底。2.2 解法二从右上角出发的线性搜索换个视角看矩阵因为行间递增所以每一列同样也是从上到下升序。那么从右上角出发会看到一个非常巧妙的现象当前值大于 target说明这一列下半部分都比 target 大可以把当前列整体排除向左走当前值小于 target说明这一行左半部分都比 target 小可以把当前行整体排除向下走。这就像在玩一个二维的“猜数字”游戏每一步都安全地排除一整行或一整列。最多走 rows columns 步就能得出答案时间复杂度 O(m n)空间 O(1)。代码也非常简洁var searchMatrix function(matrix, target) { if (!matrix.length || !matrix[0].length) return false; let row 0; let col matrix[0].length - 1; while (row matrix.length col 0) { const value matrix[row][col]; if (value target) return true; else if (value target) row; else col--; } return false; };我拿题目里的矩阵走一遍右上角是 7target 3。7 3说明最后一列所有元素都大于 3向左走到 55 3继续向左走到 33 3返回 true。三步定位。这个解法的优势是直觉好记代码不容易写错。但时间复杂度仍然不是最优因为矩阵已经整体有序了理论上应该能利用二分查找的指数级压缩能力。2.3 解法三一维映射二分查找最优解既然整个矩阵可以摊平成一个有序数组那为什么不直接在“这个虚拟的一维数组”上做二分呢问题的关键只有一个把一维索引换算出二维坐标。引出核心映射公式详细推导放在第 3 章。这里先说结论如果矩阵有 rows 行、columns 列按行优先展平后虚拟一维数组的第 index 个元素对应矩阵中的位置是const row Math.floor(index / columns); const col index % columns;有这个映射关系之后二分查找就是标准模板只是每次取值时做一次换算。时间复杂度直接降到 O(log(m*n))空间 O(1)。这是这道题最优也最经典的解法。三种解法的对比看这张表解法时间复杂度空间复杂度有序性利用程度暴力遍历O(m*n)O(1)完全不利用右上角线性搜索O(mn)O(1)部分利用一维映射二分O(log(m*n))O(1)充分利用3. 核心解法一维映射二分查找完整实现3.1 理解映射关系一维索引到二维坐标我们用一个 3 行 4 列的矩阵来验证matrix [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ];按行优先展平成一维数组是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]。展开后一维索引 0、1、2、3 落在第 0 行索引 4、5、6、7 落在第 1 行索引 8、9、10、11 落在第 2 行。规律是什么行号 Math.floor(一维索引 / columns)。比如索引 5columns 45 / 4 1.25向下取整是 1所以是第 1 行。列号 一维索引 % columns5 % 4 1即第 1 列。matrix[1][1] 对应一维索引 5值确实是 6和展平结果完全一致。我把整个映射关系列个表一维索引行号列号对应值0Math.floor(0/4)00%4011Math.floor(1/4)01%4124Math.floor(4/4)14%4057Math.floor(7/4)17%43811Math.floor(11/4)211%4312这个表看明白了映射公式就彻底掌握了。本质上就是两个运算整数除法取行号取模运算取列号。JavaScript 里 Math.floor(5 / 4) 得到 15 % 4 得到 1刚好是我们要的结果。3.2 完整代码实现与逐行说明var searchMatrix function(matrix, target) { // 防御空矩阵 if (!matrix.length || !matrix[0].length) return false; const rows matrix.length; const columns matrix[0].length; // 虚拟一维数组的左右索引边界 let left 0; let right rows * columns - 1; while (left right) { // 防止溢出的中点写法 const mid left Math.floor((right - left) / 2); // 一维索引映射回二维坐标 const row Math.floor(mid / columns); const col mid % columns; const value matrix[row][col]; if (value target) { return true; } else if (value target) { // 目标值在中点右侧 left mid 1; } else { // 目标值在中点左侧 right mid - 1; } } return false; };这段代码有四个地方必须盯紧。第一矩阵是行优先的映射时一定用 columns 做分母不是 rows。第二right 的初始值是 rows * columns - 1不是 rows * columns因为索引从 0 开始。第三while 条件用的是 left right因为初始化时 right 是合法索引不是开区间边界。第四mid 的计算用了 left Math.floor((right - left) / 2)避免 left right 潜在溢出的问题。另外我建议把映射过程单独提炼成一个小函数虽然在这道题里没有必要但养成这种习惯在更复杂的矩阵题目里会很有帮助代码可读性也会好很多。3.3 完整走查从输入到输出拿 LeetCode 的示例来完整跑一遍。矩阵是matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ]; target 3;rows 3columns 4。left 0right 11。第一次循环mid 5row 1col 1matrix[1][1] 11。11 3right 4。第二次循环mid 2row 0col 2matrix[0][2] 5。5 3right 1。第三次循环mid 0row 0col 0matrix[0][0] 1。1 3left 1。第四次循环mid 1row 0col 1matrix[0][1] 3。3 3返回 true。一共比较了 4 次。如果把矩阵扩大到 100 行 100 列暴力最坏要 10000 次一维映射二分最多约 14 次就能确定结果。数据规模越大差距越离谱这也是二分查找的魅力所在。再看一个找不到的情况target 8。第一次 mid 5matrix[1][1] 11 8right 4第二次 mid 2matrix[0][2] 5 8left 3第三次 mid 3matrix[0][3] 7 8left 4第四次 mid 4matrix[1][0] 10 8right 3。此时 left 4 right 3循环结束返回 false。4. 边界条件与二分模板细节4.1 空矩阵的防御性判断必须写在第一行很多人写二分题能顺利写对主逻辑却在边界条件上一击即溃。LeetCode 74 的输入矩阵按题目描述 m、n 都大于等于 1但在真实工程场景里或者面试官突然加一个刁钻的测试用例时空矩阵是躲不掉的。防御性判断要这么写if (!matrix.length || !matrix[0].length) return false;这里有一个细节为什么不用判断 matrix null因为 LeetCode 的函数签名传入的一定是数组。但如果你是自己在项目里封装一个通用工具函数我建议写成if (matrix null || matrix.length 0 || matrix[0].length 0)把防御范围覆盖到所有可能出现的异常输入。还有一点要特别注意matrix[0] 在!matrix.length为 false 的时候访问是安全的。JavaScript 的 || 运算符有短路特性前半句为 true 时后半句根本不会执行。所以这个判断虽然看着简单但运行顺序是经过设计的。4.2 左闭右闭模板的正确姿势我在上文的代码里用的是左闭右闭写法也就是区间 [left, right] 同时包含两端。这种写法简单直观配合 while (left right) 使用right 初始化为 rows * columns - 1收缩时 left mid 1、right mid - 1。另一个常见模板是左闭右开写法 [left, right)right 初始化为 rows * columns循环条件是 left right收缩时 right mid。这个模板常见于寻找左边界的场景比如 LeetCode 278 第一个坏版本。但在 LeetCode 74 这种“判断是否存在”的场景里左闭右闭最直观也最不容易绕晕。我的建议是先把左闭右闭这一个模板彻底练熟。原因很简单它和“查找目标值”的语义天然匹配每一步都检查 mid 指向的值等于就返回不等于就缩小范围很难写出死循环。等这个模板形成肌肉记忆之后再去接触左闭右开就不会把两者混淆了。4.3 单行、单列和极端值的表现当矩阵只有一行比如 [[1, 3, 5, 7]]rows 1right 3。映射的时候Math.floor(mid / 4) 永远等于 0mid % 4 就是列号。一维映射法自动退化成普通的一维数组二分非常优雅。当矩阵只有一列比如 [[1], [10], [23]]columns 1。映射公式变成 row Math.floor(mid / 1) midcol mid % 1 0又退化成在单列里做二分。两种退化场景都不需要写额外分支这就是一维映射法的一个隐藏优点结构统一不搞特殊化。极端值方面如果 target 比矩阵第一个元素还小left 会一直收缩到 left right返回 false如果 target 比矩阵最后一个元素还大right 会一直收缩到 left right返回 false。两种情况都会被 while (left right) 正确捕获不需要额外特判。4.4 一个容易忽略的常识right 是索引不是数量我见过不少人在初始化 right 时写成 rows * columns然后第一次取 matrix[row][col] 就数组越界。这是因为把“元素个数”和“最大索引”搞混了。一个长度为 12 的数组合法下标是 0 到 11。所以 right 永远是 rows * columns - 1。这个错位非常隐蔽尤其是当矩阵恰好是 1 行 1 列时rows * columns 1right 写成 1 也不会报错因为 mid Math.floor((0 1) / 2) 0刚好没越界bug 被藏起来了。但矩阵变成 1 行 2 列时right 2mid 1matrix[0][1] 没问题再变成 1 行 3 列right 3mid 1matrix[0][1] 也没问题因为你可能运气好没踩到边界。这种隐藏 bug 最危险因为测试用例不全的时候它根本不会暴露。5. 常见错误与排查实录5.1 错误一映射公式的分母用混我在帮别人 review 代码时不只一次看到row Math.floor(mid / rows)或者 col mid % rows。一旦写错在矩阵不是方阵的情况下索引会完全错乱要么访问到错误的值要么直接越界报错。正确理解的关键在于“按行优先展平”这个动作。一维数组里每连续 columns 个元素构成一行所以除以 columns商是行号余数是列号。你可以随手画一个 3 行 4 列的矩阵把一维索引标在每个格子外面再对照公式看一眼。这个错误基本就是一次性问题看过一次就再也不会犯了。5.2 错误二空矩阵时直接取 matrix[0].length有同学防御性判断只写了if (!matrix.length) return false下一行又写const columns matrix[0].length。如果 matrix 是 [[]]matrix.length 是 1能通过第一层判断但 matrix[0].length 是 0。columns 变成 0 之后right rows * 0 - 1 -1循环直接不执行返回 false结果倒是没错。但如果在 columns 0 的基础上继续计算 matrix[0][0]代码就会当场崩溃。最稳的写法是if (!matrix.length || !matrix[0].length) return false;两个条件写一行利用短路特性既安全又简洁。5.3 错误三无限循环或错过答案二分查找最怕的就是死循环。左闭右闭模板下死循环通常来自收缩步骤写错比如某一步写成 left mid 而不是 left mid 1。当 left 和 right 相邻时mid 会等于 left如果又让 left mid区间永远不会缩小循环就卡死了。排查方法很简单在 while 循环里打印 left、right、mid看哪一步没有按预期收缩。这种问题调试一次就能记住以后写二分基本不会重犯。5.4 错误四忽略了 columns 在映射中的关键作用还有一种情况代码看着都对但 target 刚好在矩阵中时却返回 false。我在本地调试后发现有人在计算列号时写的是col mid % rows而不是mid % columns。在 rows 和 columns 相等时比如 3 行 3 列这个错误不会暴露。一旦换成 3 行 4 列索引映射就全歪了。所以做题时最好先确认矩阵不是方阵的情况测试用例里加一个非方阵用例能有效暴露这类问题。6. 延伸思考与面试追问6.1 变式题行列分别有序但不再整体升序LeetCode 240 是这道题最经典的变式。它把矩阵条件改成每一行从左到右升序每一列从上到下升序但不再保证“每行第一个整数大于前一行最后一个整数”。这时候矩阵不能被整体展平成一维有序数组一维映射二分直接失效。正确解法是右上角指针法也就是我前面在 2.2 节写过的思路。从右上角出发当前值比 target 大就往左比 target 小就往下时间复杂度 O(m n)。很多人在面试时会把 LeetCode 74 的解法硬套到 240 上结果发现逻辑不成立。所以判断“矩阵是否整体有序”永远是做题的第一步。6.2 追问能不能做到 O(log m log n)有的面试官会接着问矩阵整体有序能不能先对行做二分找到目标值所在的行再对该行做二分这样时间复杂度是 O(log m log n)系数上比 O(log(m*n)) 更优。实现思路是第一步在每行首元素组成的数组上做二分找到最后一个首元素小于等于 target 的行第二步在该行内做普通二分。代码是这样的var searchMatrix function(matrix, target) { if (!matrix.length || !matrix[0].length) return false; const rows matrix.length; const columns matrix[0].length; // 第一步在每行首元素组成的数组上二分 let low 0; let high rows - 1; while (low high) { const mid low Math.floor((high - low) / 2); if (matrix[mid][0] target) return true; else if (matrix[mid][0] target) low mid 1; else high mid - 1; } // 循环结束后 high 指向最后一个首元素 target 的行 const candidateRow high; if (candidateRow 0) return false; // 第二步在候选行内做普通二分 let left 0; let right columns - 1; while (left right) { const mid left Math.floor((right - left) / 2); if (matrix[candidateRow][mid] target) return true; else if (matrix[candidateRow][mid] target) left mid 1; else right mid - 1; } return false; };这个方案写起来比一维映射复杂但它展现了更强的分析能力。面试时如果时间充裕能把两种写法都讲清楚绝对是一个加分项。6.3 工程场景中的联想这道题虽然看起来是纯算法题但“一维映射 有序查找”的思路在工程中并不少见。比如游戏开发里按行优先存储的二维地图就是网格展平成一维数组的一个典型场景再比如按时间分片的日志存储多个有序文件拼接起来在逻辑上构成一个更大的有序序列你要按时间戳查找一条日志完全可以套用同样的虚拟索引思路。算法训练的意义有时候不在于背模板而在于培养这种抽象能力看到一个二维结构能意识到它可以被视作某种一维序列看到一个无序集合能意识到加一个索引之后就可以二分。这些迁移思维才是刷题真正带给你的回报。另外如果你正在准备面试可以把这道题的三种解法、时间复杂度、边界条件写在一页笔记里反复默写。二分查找是高频考点LeetCode 74 是二分里非常基础的一道吃透它之后LeetCode 33、153、240 这些变式做起来都会顺手很多。最后分享一点我的个人体会。刷题这些年我最大的感受是算法题不是比谁背得多而是比谁在边界条件上更稳。LeetCode 74 的核心逻辑只有十行左右但真正拉开两个候选人差距的往往就是空矩阵判断、right 初始化、映射分母这三个细节。把这些细节形成肌肉记忆之后你再去做其他二分题会明显感觉到自己“稳”了很多。