240. 搜索二维矩阵 II（Search a 2D Matrix II）
频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯/美团
题目
m×n 矩阵，每行从左到右升序，每列从上到下升序，判断 target 是否存在。与 74 题不同，本题不保证每行第一个元素大于上一行最后一个（即全局不完全有序）。
示例：
输入:
[
[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
target = 20 → false
思路
Z 字形查找（右上角出发）：从右上角 (0, n-1) 开始，每次比较当前值与 target：
- 相等 → 找到，返回 true
- 当前值 < target → 下移一行（该行左侧都更小，整行排除）
- 当前值 > target → 左移一列（该列下方都更大，整列排除）
每次排除一行或一列，至多 m+n 步。
代码
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;
int m = matrix.length, n = matrix[0].length;
int r = 0, c = n - 1; // 从右上角出发
while (r < m && c >= 0) {
if (matrix[r][c] == target)
return true;
if (matrix[r][c] < target)
r++; // 排除当前行
else
c--; // 排除当前列
}
return false;
}复杂度
- 时间：O(m + n) —— 最多走 m 行 + n 列
- 空间：O(1)
边界条件
- 空矩阵：返回 false，开头防御
- 单行单列：走水平或垂直一条线即可
- target 小于矩阵最小值或大于最大值：从右上角出发会一路左移或下移到边界，返回 false
变式
- 74. 搜索二维矩阵：全局有序，可用一次二分 O(log(mn))
- 每行分别二分：遍历每一行做二分，O(m log n)；适用于 m << n 的场景
- 从左下角出发：对称思路，当前值 < target 右移，当前值 > target 上移
易错点
- 本题不能用一维二分（全局不完全有序，74 题才适用），但可以每行单独二分
- 从右上角出发时，矩阵为空或第一行为空都会导致
matrix[0].length空指针，必须前置判空 - 移动方向容易搞反：matrix[r][c] < target → 向下（行号增大），> target → 向左（列号减小）
面试追问
- 从左上角或右下角出发行不行？ 不行——左上角向右向下都增大，右下角向左向上都减小，无法判断往哪个方向走。只有右上（左小下大）和左下（上小右大）两个拐角能提供唯一决策方向
- 怎么证明每次排除一行/列的正确性？ 右上角 matrix[r][c] 是当前行最大、当前列最小。如果 target > matrix[r][c]，说明 target 大于整行最大，所以整行不可能有 target，r++ 排除该行；如果 target < matrix[r][c]，说明 target 小于整列最小，所以整列不可能有 target，c— 排除该列。每次排除的都是「不可能区域」
- m 远大于 n 或反之时怎么优化？ 对短的维度做二分：如果 m > n，可以遍历行二分列（O(m log n)），或遍历列二分行（O(n log m)），选短的那维做外层遍历
关联题
- 基础：74. 搜索二维矩阵 —— 全局有序版本的二分搜索
- 同套路：4. 寻找两个正序数组的中位数 —— 分治排除不可能是答案的一半
- 知识点：利用矩阵行/列有序性的排除法，见数组与字符串