二分与排序中等2 种解法
#240搜索二维矩阵 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.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-109 <= target <= 109
解题主线
- 每一行本身有序，可以独立二分；行之间的列序关系还可进一步利用。
- 右上角同时是所在行最大方向的端点和所在列最小方向的端点：值过大就左移，过小就下移。
- 阶梯搜索每一步排除一整行或一整列，因此最多移动 m + n 次。
解法 1：逐行二分查找
对每个有序行执行标准二分；任一行命中即返回。
-
时间复杂度： O(m log n)
-
空间复杂度： O(1)
final class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// 读取首行长度前先排除空矩阵与空行。
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
for (int[] row : matrix) {
int left = 0;
int right = row.length - 1;
// 搜索区间始终为闭区间 [left, right]。
while (left <= right) {
int middle = left + (right - left) / 2;
if (row[middle] == target) return true;
if (row[middle] < target) left = middle + 1;
else right = middle - 1;
}
}
return false;
}
}解法 2：右上角阶梯搜索
从右上角出发：当前值大于 target 就排除当前列并左移，小于 target 就排除当前行并下移。
-
时间复杂度： O(m + n)
-
空间复杂度： O(1)
final class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// 阶梯搜索需要有效的右上角起点。
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int row = 0;
int column = matrix[0].length - 1;
// 未排除区域始终位于当前位置的左下方。
while (row < matrix.length && column >= 0) {
int value = matrix[row][column];
if (value == target) return true;
// 当前值过大可排除整列，过小可排除整行。
if (value > target) column--;
else row++;
}
return false;
}
}边界与易错点
- 本题各行首元素不保证大于上一行尾元素，不能像第 74 题那样把矩阵整体拉平成有序数组。
- 旧文件两个逐行二分实现算法同构，整理后合并为一个。
- 读取 matrix[0] 前必须处理空矩阵。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/medium/Q240_searchMatrixII.java