第 240 题中等

搜索二维矩阵 II

Search a 2D Matrix II

在每行从左到右递增、每列从上到下递增的矩阵里，判断 target 是否存在。

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10⁹ <= matrix[i][j] <= 10⁹
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10⁹ <= target <= 10⁹

解题思路

主解法

右上角 · 阶梯搜索

把右上角当成一行的最大、一列的最小，每次砍掉一行或一列

从左上角出发，右边和下边都比当前值大，无法判断该往哪走；从右上角出发就不一样：它是本行最大、本列最小。

当前值大于 target：这一列从它往下都更大，整列可以排除，c--。
当前值小于 target：这一行从它往左都更小，整行可以排除，r++。

分步图解

(0,4) 是 19，比目标大；这一列往下只会更大，整列排除，当前位置移到 (0,3)。

target: 17

剩余搜索区：第 0 行以下、第 4 列以左

行列都递增；每比较一次，灰色区域至少少一行或一列。

当前位置

r=0c=4matrix[r][c]=19

1 / 4

右上角比目标大就左移，比目标小就下移；剩余矩形每次只保留一边。

自拟矩阵是 4×5，target = 17 位于左下区域，路径先向左排掉两列，再向下排掉三行。蓝色格子是当前比较位置，灰色是已经不可能包含答案的区域。

每一步至少少一行或一列，所以最多走 m + n 步。这个性质只要求行列分别有序，不要求整个矩阵按行优先完全有序；后者才能用一维二分。

时间 O(m + n)空间 O(1)

易错点

从左上角出发：右边和下边都更大，无法决定移动方向。
排除整列时写成 r--：行方向已经到顶，越界后循环立刻结束。
把本题当成第 74 题用一维二分：只有“整体按行展开有序”时才能那样做，本题没有这个条件。

对照解法

逐行二分

每行单独二分，简单但不是本题想要的利用方式

结果正确，O(m log n) 也能通过，但完全没有利用列递增；仅作为“只会二分时”的保底对照。

既然每一行都有序，就对每一行做一次 binary_search。在最坏情况下要走完所有行，复杂度 O(m log n)。

它的优点是实现几乎不会错；缺点是丢掉列信息，如果矩阵很扁（m 很大、n 很小），会比阶梯搜索慢一个数量级。

面试时可以先说这个保底方案，再补上阶梯搜索，说明为什么后者更贴合题目的两条有序约束。

1遍历每一行。
2在该行内二分查找 target。
3任意一行命中就返回 true。
4全部行结束返回 false。

时间 O(m log n)空间 O(1)

易错点

行内二分边界写成开区间却仍用 <=，可能死循环。
忘记利用列递增，在最坏情况下多做大量比较。

代码与演示

主解法配有图解；对照解法用于比较思路、复杂度或实现方式。

演示输入matrix = [[2,5,9,12,19],[3,6,11,14,21],[7,10,15,18,24],[8,13,17,20,26]], target = 17

从右上角出发：它是本行最大值、本列最小值，一次比较就能排除一整行或一整列。