74_搜索二维矩阵[MEDIUM]
约 1215 字大约 4 分钟
2026-02-26
给你一个满足下述两条属性的 m x n 整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。
示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true示例 2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false题目解析
这道题目的核心在于理解矩阵的两个特性:
- 每行内部是有序的(从左到右递增)。
- 相邻行之间也是有序的(每行的第一个元素大于上一行的最后一个元素)。
结合这两个条件,我们可以得出一个非常重要的结论:如果将这个二维矩阵按行拼接展平,它实际上就是一个严格递增的一维有序数组。
因此,题目本质上就是让我们在一个有序数据结构中查找特定目标值,这非常适合使用二分查找(Binary Search)。
解题思路
对于这道题,主要有以下三种解法。作为面试官,我通常期待候选人能直接想到前两种,并能清楚地说明第一种解法是最优的。
方法一:全局二分查找(最优解,虚拟一维数组映射)
既然矩阵可以看作一个展开的一维有序数组,我们可以虚拟地把它拉平,直接进行一次二分查找。
- 假设矩阵有
m行n列,那么总共有m * n个元素。 - 我们将一维数组的索引区间设为
[0, m * n - 1]。 - 对于一维数组中的任意索引
mid,我们可以通过数学运算将其映射回二维矩阵的坐标:- 行号
row = mid / n - 列号
col = mid % n
- 行号
- 通过坐标拿到矩阵对应的值
matrix[row][col]后,与target比较即可。
复杂度分析:
- 时间复杂度:O(log(m×n)),标准的二分查找时间复杂度。
- 空间复杂度:O(1),仅使用了常数级别的额外指针。
方法二:两次二分查找
如果考虑到极端情况下矩阵非常大(例如 m×n 超过了 32 位整数最大值 Integer.MAX_VALUE,当然本题中规模只有 104,不存在此问题),虚拟一维数组的索引可能会溢出。此时可以通过两次二分查找来解决:
- 第一步:对矩阵的第一列(或者每一行的最后一个元素)进行二分查找,找到
target可能落在哪一行。 - 第二步:在锁定行内部进行标准的二分查找。 复杂度分析:时间同样是 O(logm+logn)=O(log(mn)),空间 O(1)。
方法三:右上角/左下角向内搜索(Z字形搜索)
这是 LeetCode 240题「搜索二维矩阵 II」的经典解法。本题虽然多了一个“下一行首大于上一行尾”的条件,但同样适用。
- 从矩阵的右上角开始搜索,如果当前值大于目标值,向左移动一列;如果当前值小于目标值,向下移动一行。 复杂度分析:时间复杂度是 O(m+n),不如二分查找优,不推荐作为本题的首选。
Java 实现
方法一(全局二分查找)
class Solution {
/**
* 搜索二维矩阵
*
* @param matrix 给定的二维矩阵
* @param target 需要查找的目标值
* @return 如果 target 存在返回 true,否则返回 false
*/
public boolean searchMatrix(int[][] matrix, int target) {
// 防御性编程:处理边界条件
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length; // 矩阵的行数
int n = matrix[0].length; // 矩阵的列数
// 二分查找的左右边界(将二维矩阵视为长度为 m*n 的一维数组)
int left = 0;
int right = m * n - 1;
// 开始标准的二分查找
while (left <= right) {
// 防止 (left + right) 导致整型溢出的写法
int mid = left + (right - left) / 2;
// 核心逻辑:将一维数组的索引转化为二维矩阵的横纵坐标
// mid / n 得到所在行,mid % n 得到所在列
int midValue = matrix[mid / n][mid % n];
if (midValue == target) {
// 找到了目标值
return true;
} else if (midValue < target) {
// 当前值小于目标值,说明目标在右侧(后半部分)
left = mid + 1;
} else {
// 当前值大于目标值,说明目标在左侧(前半部分)
right = mid - 1;
}
}
// 循环结束还未找到,说明 target 不在矩阵中
return false;
}
}