题目

给定一个m x n整数矩阵matrix，它满足：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给定整数target，判断它是否存在于矩阵中。题目要求时间复杂度为O(log(m * n))。

初始思路：逐行二分

最直接的做法是遍历每一行，再对当前行进行二分查找。单行二分的时间复杂度是O(log n)，一共需要检查m行，因此总时间复杂度为：

O(m log n)

这个复杂度没有达到题目要求的O(log(m * n))。另外，如果在遍历第一行时就直接返回查找结果，程序实际上只会检查第一行，后面的行不会被访问。

问题的关键不是如何对每一行分别二分，而是能否只对整个矩阵做一次二分。

核心观察：矩阵按行展开后整体有序

第一条性质保证每一行内部有序，第二条性质又保证下一行的第一个元素大于上一行的最后一个元素。因此，把各行首尾相接后，可以得到一个长度为m * n的有序一维数组。

例如：

matrix = [ [ 1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] 按行展开： [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

不需要真的创建这个一维数组，只需要建立一维下标和二维坐标之间的映射。

一维下标如何映射到矩阵

设矩阵每行有n个元素，对于虚拟一维数组中的下标mid：

行号 = mid / n 列号 = mid % n

因此，一维数组中的nums[mid]可以写成：

matrix[mid / n][mid % n]

以每行3个元素为例：

第 0 行：一维下标 0 1 2 第 1 行：一维下标 3 4 5 第 2 行：一维下标 6 7 8

当mid = 5时，5 / 3 = 1、5 % 3 = 2，所以它对应第1行第2列。

二分目标：寻找第一个>= target的位置

采用开区间哨兵写法，初始化：

l = -1 r = m * n

二分过程中维护以下不变量：

l 指向的元素 < target r 指向的元素 >= target

-1和m * n都是虚拟哨兵，不对应真实元素，因此不能访问它们。每次取中点后：

• 如果中点元素< target，令l = mid。
• 如果中点元素>= target，令r = mid。

当循环结束时，r == l + 1，两者之间已经没有未检查的位置，所以r是第一个大于等于target的下标。

代码实现

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int l = -1; int r = m * n; while (r > l + 1) { int mid = l + (r - l) / 2; if (matrix[mid / n][mid % n] < target) { l = mid; } else { r = mid; } } if (r >= m * n) { return false; } return matrix[r / n][r % n] == target; } }

为什么要先判断r >= m * n

当矩阵中的所有元素都小于target时，二分过程中找不到任何大于等于target的真实元素，r会一直保持为虚拟右哨兵m * n。

这个下标已经超出矩阵范围。如果直接访问matrix[r / n][r % n]，就会发生数组越界。因此，访问结果位置之前必须先确认：

r < m * n

如果r是有效下标，再判断该位置的元素是否恰好等于target。因为r只是第一个大于等于target的位置，它也可能指向一个大于target的元素。

复杂度

虚拟一维数组共有m * n个元素，每轮二分都将搜索范围缩小约一半，因此时间复杂度为O(log(m * n))。算法只使用常量级变量，没有创建真正的一维数组，所以空间复杂度为O(1)。

总结

这道题的关键是利用两条有序性质，把二维矩阵视为一个整体有序的一维数组：

1. 用mid / n得到行号，用mid % n得到列号。
2. 在[0, m * n)对应的虚拟数组上执行一次二分查找。
3. 使用哨兵写法时，明确维护l侧< target、r侧>= target的不变量。
4. 结果下标可能等于m * n，访问矩阵前必须先进行边界检查。

以后遇到“二维结构整体有序”且复杂度要求为O(log(m * n))的题目，可以优先考虑是否能通过下标映射，把问题转化为标准的一维二分查找。