LeetCode 74. 搜索二维矩阵
目录
题目描述
题意分析
给定一个 $m \times n$ 的整数矩阵和一个目标值
target，判断target是否存在于矩阵中，只需返回布尔值，不需要给出位置。题目给的两条性质要连起来读：一是「每行中的整数从左到右升序」，二是「每行的第一个整数大于前一行的最后一个整数」。第一条保证了行内有序，第二条把相邻两行首尾接了起来。两条合在一起的效果是——把矩阵按行拼接成一条长序列后，这条序列整体严格升序，没有任何一处断裂或回落。换句话说，这个矩阵只是一个一维有序数组换了种排版方式，二维只是外观。
这一点必须和第 240 题分清楚。240 题只保证行内升序、列内升序，不保证跨行衔接，比如第二行的开头完全可能比第一行的结尾小，因此它按行展开后并不有序，本题的做法在那里是错的。
约束方面，$m$ 和 $n$ 均至少为 $1$，所以不必担心空矩阵；元素值域跨度较大，$m \cdot n$ 在 $int$ 范围内不会溢出。需要考虑的边界是：单行矩阵、单列矩阵、
target小于左上角或大于右下角这类必然不存在的情况——它们都会被统一的二分逻辑自然处理掉，不需要特判。
解法：虚拟一维数组二分查找
核心思路
问题关键：每行内部升序，且下一行首元素大于上一行末元素。按行展开后，矩阵就是一个长度为
m * n的严格递增数组，可以直接整体二分。为什么用虚拟一维下标：真正展开矩阵需要 $O(mn)$ 时间和空间，反而失去二分的意义。对虚拟下标
\[row = idx / n, \quad col = idx \bmod n\]idx，按一行有n个元素做带余除法：因此可用
matrix[mid/n][mid%n]在 $O(1)$ 时间读取虚拟数组的中间值。不变量与正确性：每轮开始时，若目标存在，其虚拟下标一定在闭区间
[left,right]中。中间值小于目标时，整体有序保证[left,mid]都可排除；大于目标时可排除[mid,right]。区间不断缩小，命中时返回true，区间为空时说明目标不存在。
解题步骤
- 令
left = 0、right = m*n-1，表示虚拟数组的闭区间。- 当
left <= right时，计算mid = left + (right-left)/2。- 通过
matrix[mid/n][mid%n]取得中间值。- 相等时返回
true；中间值较小时令left = mid+1，否则令right = mid-1。- 区间为空后返回
false。例如样例矩阵查找 3 时，虚拟下标区间依次为
[0,11] -> [0,4] -> [0,1] -> [1,1]，最终在matrix[0][1]命中。
代码实现
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
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 value = matrix[mid / n][mid % n];
if (value == target) {
return true;
}
if (value < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
left, right := 0, m*n-1
for left <= right {
mid := left + (right-left)/2
value := matrix[mid/n][mid%n]
if value == target {
return true
}
if value < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
复杂度分析
- 时间复杂度：$O(\log(mn))$，每轮将
m*n大小的搜索区间减半。- 空间复杂度：$O(1)$，只维护常数个下标变量。
关键点总结
- 两条有序条件合在一起，才能保证按行展开后全局有序。
- 虚拟下标映射中的除数和模数都是列数
n。- 闭区间模板要配套使用：
right = m*n-1、left <= right、更新mid ± 1。- 240 题没有“下一行首元素大于上一行末元素”，不能使用整体二分。
易错点总结
- 映射时使用行数
m：非方阵中会读错位置甚至越界，必须按每行长度n换算。right初始化为m*n：这个下标不属于虚拟数组。- 闭区间循环漏掉等号：单元素区间不会被检查，
[[1]]查找 1 会返回false。- 更新为
left = mid或right = mid：中间位置没有被排除，区间可能无法收缩。- 先复制成一维数组：虽能得到正确结果，但构造过程已经需要 $O(mn)$ 时间和空间。
- 照搬到 240 题：其按行展开后不保证有序，二分前提不成立。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 240. 搜索二维矩阵 II | 中等 | 无跨行衔接，改用右上角阶梯排除 |
| 剑指 Offer 04. 二维数组中的查找 | 中等 | 与 240 同型，阶梯法的直接练习 |
| 面试题 10.09. 排序矩阵查找 | 中等 | 同型题换皮，检验模板熟练度 |
| 35. 搜索插入位置 | 简单 | 一维闭区间二分的边界基本功 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 二分对象从下标换成值域 |