这道题的核心考点是「二分查找」。
核心思路：二维矩阵降维为一维数组
题目给出了矩阵的两个关键特性：
这意味着，如果我们把这个二维矩阵按行顺序“拉直”，它就是一个完全升序的一维数组。因此，我们可以直接在这个“虚拟的一维数组”上进行标准的二分查找。
具体步骤如下：
- 计算中间索引 mid = left + (right – left) / 2（这种写法可以防止整数溢出）。
- 关键转换：将一维索引 mid 映射回二维矩阵的坐标：
- 行号：row = mid / n
- 列号：col = mid % n
- 比较 matrix[row][col] 与目标值 target：
- 相等：找到目标，返回 true。
- 小于 target：说明目标在右半区，调整左边界 left = mid + 1。
- 大于 target：说明目标在左半区，调整右边界 right = mid – 1。
Java 代码实现
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// 1. 边界处理：矩阵为空的情况
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length; // 矩阵行数
int n = matrix[0].length; // 矩阵列数
// 2. 初始化一维数组的左右边界
int left = 0;
int right = m * n – 1;
// 3. 二分查找
while (left <= right) {
// 防止溢出的中点计算方式
int mid = left + (right – left) / 2;
// 将一维索引转换为二维矩阵的行列坐标
int row = mid / n;
int col = mid % n;
if (matrix[row][col] == target) {
return true; // 找到目标值
} else if (matrix[row][col] < target) {
left = mid + 1; // 目标在右半部分
} else {
right = mid – 1; // 目标在左半部分
}
}
return false; // 未找到目标值
}
}
复杂度分析
- 时间复杂度：O(log(m times n))。我们将包含 m times n 个元素的矩阵视为一维数组进行二分查找，每次比较都能将搜索范围缩小一半。
- 空间复杂度：O(1)。只使用了几个指针变量（left, right, mid, row, col），没有使用额外的线性数据结构。
💡 避坑指南
- 索引映射公式：row = mid / n 和 col = mid % n 是这道题的灵魂，一定要除以列数 n，千万不要和行数 m 搞混了。
- 防止溢出：在计算 mid 时，推荐使用 left + (right – left) / 2 而不是 (left + right) / 2，这在数组长度极大时能有效避免整型溢出。
- 空值判断：LeetCode 的测试用例中经常包含空矩阵（如 [] 或 [[]]），在代码开头加上空值判断可以避免 NullPointerException。
这种“降维打击”的思路在矩阵题里非常巧妙。接下来要不要看看进阶版 LeetCode 240. 搜索二维矩阵 II？那题的矩阵性质稍有不同，需要用到一种非常直观的“Z字形搜索”策略！
