搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。
你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。
示例 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
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
解法一（两次二分）：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
// 第一次二分：找到最大的行 row，使得 matrix[row][0] <= target
int top = 0;
int bottom = m - 1;
int row = -1;
while (top <= bottom)
{
int mid = top + (bottom - top) / 2;
if (matrix[mid][0] <= target)
{
row = mid;
top = mid + 1;
}
else
{
bottom = mid - 1;
}
}
if (row == -1)
{
return false;
}
// 第二次二分：在 row 这一行内查找 target
int left = 0;
int right = n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (matrix[row][mid] == target)
{
return true;
}
else if (matrix[row][mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return false;
}
};
解法二（一次二分）：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
int left = 0;
int right = m * n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
int val = matrix[mid / n][mid % n];
if (val == target)
{
return true;
}
else if (val < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return false;
}
};
核心思想
这题要求时间复杂度 O(log(m * n))，看到这个限制，第一时间就想到二分查找。
普通二分只能在一维有序数组上做，但这题给的是二维矩阵。
不过这题的第二个属性很关键：
每行的第一个整数大于前一行的最后一个整数。
这意味着，把矩阵的每一行按顺序首尾相接，得到的其实是一个整体有序（非严格递增）的一维数组。
例如：
[[1, 3, 5, 7],
[10,11,16,20],
[23,30,34,60]]
按行拼接后是：
[1,3,5,7,10,11,16,20,23,30,34,60]
这是一个完全有序的数组。
所以问题就转化成了：在长度为 m * n 的有序数组上做二分查找。
解法一：两次二分
两次二分的思路更直观：先确定目标值在哪一行，再在这一行里二分查找。
第一次二分：定位行
由于每一行的第一个元素 matrix[row][0] 随着行号递增也严格递增，所以第一列本身就是一个有序数组。
我们要找的是「最大的那个行号 row，使得 matrix[row][0] <= target」。
int top = 0;
int bottom = m - 1;
int row = -1;
while (top <= bottom)
{
int mid = top + (bottom - top) / 2;
if (matrix[mid][0] <= target)
{
row = mid;
top = mid + 1;
}
else
{
bottom = mid - 1;
}
}
循环结束后，row 就是满足条件的最大的行号。
如果 target 比第一行的第一个元素还小，那么 row 保持 -1，说明 target 不可能在矩阵中，直接返回 false。
第二次二分：行内查找
确定了目标行 row 之后，就在这一行内做普通的二分查找：
int left = 0;
int right = n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (matrix[row][mid] == target)
{
return true;
}
else if (matrix[row][mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
解法二：一次二分
一次二分更简洁，直接把矩阵当成一个长度为 m * n 的一维数组来二分。
关键是要能把一维下标映射回二维坐标。
假设一维下标是 idx，它对应的二维坐标是：
row = idx / n
col = idx % n
其中 n 是矩阵的列数。
理解起来也很自然：一行有 n 个元素，所以前 n 个下标属于第 0 行，接着 n 个属于第 1 行，依此类推。
于是二分的过程和普通二分完全一样：
int left = 0;
int right = m * n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
int val = matrix[mid / n][mid % n];
if (val == target)
{
return true;
}
else if (val < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
每次比较前，先用 mid / n 和 mid % n 把一维下标转成二维坐标，再取到对应元素。
坐标映射为什么正确
把矩阵按行展开成一维数组，长度为 m * n。
一维下标 idx 从 0 到 m * n - 1。
因为每一行有 n 个元素：
- 第
0行的元素对应下标0到n - 1 - 第
1行的元素对应下标n到2n - 1 - 第
r行的元素对应下标r * n到(r + 1) * n - 1
所以：
- 行号
row = idx / n，表示idx前面完整地排满了多少个n - 列号
col = idx % n，表示idx在当前行内排在第几个位置
因此 matrix[idx / n][idx % n] 恰好就是一维数组中下标 idx 对应的矩阵元素。
为什么可以整体二分
普通二分要求数组整体有序。
这题的第一条属性只保证了「每一行内部」有序，光靠它还不能把矩阵整体看成有序数组。
但第二条属性「每行的第一个整数大于前一行的最后一个整数」把各行之间的顺序也固定了：
第
i行里的任意元素都小于第i + 1行里的任意元素。
所以把矩阵按行首尾相接后，得到的数组整体满足：
matrix[0][0] <= ... <= matrix[0][n-1] <= matrix[1][0] <= ... <= matrix[m-1][n-1]
这是一个非严格递增的有序数组。
因此可以放心地在它上面做二分。
边界情况
如果 target 比矩阵中最小的元素还小，例如小于 matrix[0][0]：
- 一次二分中，
right会不断左移直到left > right，返回false - 两次二分中，第一次二分找不到满足条件的行，
row == -1，返回false
如果 target 比矩阵中最大的元素还大：
- 一次二分中，
left会不断右移直到越界，返回false - 两次二分中，第一次二分会把
row定位到最后一行，第二次行内二分找不到，返回false
如果 target 恰好等于某一行第一个或最后一个元素，两次二分和一次二分都能正确返回 true。
题目提到「非严格递增」，说明同一行内可能存在重复元素，但整体仍然有序，所以二分查找依然正确。
正确性证明
我们证明：算法返回的结果满足题意。
结论 1：矩阵按行首尾相接后是一个非严格递增的一维数组
由第一条属性，每一行内部非严格递增，所以：
matrix[i][0] <= matrix[i][1] <= ... <= matrix[i][n-1]
由第二条属性，每行的第一个整数大于前一行的最后一个整数，所以：
matrix[i-1][n-1] < matrix[i][0]
把这两条拼接起来，得到：
matrix[i-1][n-1] <= matrix[i][0]
因此整个按行展开的数组从头到尾非严格递增，是整体有序的。
结论 2：一次二分的坐标映射正确
对于一维下标 idx，其行号满足 row = idx / n，列号满足 col = idx % n。
因为第 row 行对应的一维下标范围是 [row * n, row * n + n - 1]，所以：
idx = row * n + col
其中 0 <= col < n。
这正是整数除法 idx / n = row、取余 idx % n = col 的数学含义。
因此 matrix[idx / n][idx % n] 准确对应一维下标 idx 处的元素。
结论 3：一次二分能正确判断 target 是否存在
由结论 1，按行展开的一维数组整体有序。
由结论 2，每次取 matrix[mid / n][mid % n] 就是取这个有序数组中下标 mid 处的元素。
标准二分查找在有序数组上是正确的，所以一次二分能正确判断 target 是否存在。
结论 4：两次二分能正确找到目标行，并在行内正确查找
第一次二分在第一列（有序数组）上，找到满足 matrix[row][0] <= target 的最大行号 row。
如果 target 存在于矩阵中，它所在的行 r 一定满足 matrix[r][0] <= target。
而由于第 r + 1 行的第一个元素大于第 r 行的最后一个元素，即 matrix[r+1][0] > matrix[r][n-1] >= target，所以 matrix[r+1][0] > target。
因此目标行 r 恰好就是满足 matrix[row][0] <= target 的最大行号，第一次二分能正确定位到它。
第二次二分在目标行这个有序数组上做标准二分，能正确判断 target 是否在该行内。
得出结论
由结论 3 可知，一次二分解法正确。
由结论 4 可知，两次二分解法正确。
因此两个解法都能在 O(log(m * n)) 时间内正确判断 target 是否存在。
举例理解
以：
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target = 3
为例，看一次二分的过程。
这里 m = 3，n = 4，一维数组长度为 12。
展开后的有序数组是：
下标： 0 1 2 3 4 5 6 7 8 9 10 11
元素： 1 3 5 7 10 11 16 20 23 30 34 60
二分过程：
left = 0，right = 11，mid = 5，对应matrix[1][1] = 11，11 > 3，right = 4left = 0，right = 4，mid = 2，对应matrix[0][2] = 5，5 > 3，right = 1left = 0，right = 1，mid = 0，对应matrix[0][0] = 1，1 < 3，left = 1left = 1，right = 1，mid = 1，对应matrix[0][1] = 3，3 == 3，返回true
如果 target = 13：
- 二分过程中每次都排除了不包含
13的一半区间 - 最终
left > right，循环结束，返回false
复杂度分析
解法一
第一次二分在第一列上查找，范围是 m 行。
第二次二分在目标行上查找，范围是 n 列。
所以时间复杂度是：
O(log m + log n)
即 O(log(m * n))。
算法只使用了常数个变量。
- 时间复杂度：
O(log(m * n)) - 空间复杂度：
O(1)
解法二
在一维数组长度为 m * n 上做标准二分。
- 时间复杂度：
O(log(m * n)) - 空间复杂度：
O(1)
其中 m、n 分别是矩阵的行数和列数。
两种解法都满足题目要求的 O(log(m * n)) 时间。
一次二分更简洁，是推荐写法。