74. 搜索二维矩阵：把二维结构映射成一维后做二分
题目
给定一个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)。
总结
这道题的关键是利用两条有序性质，把二维矩阵视为一个整体有序的一维数组：
- 用
mid / n得到行号，用mid % n得到列号。 - 在
[0, m * n)对应的虚拟数组上执行一次二分查找。 - 使用哨兵写法时，明确维护
l侧< target、r侧>= target的不变量。 - 结果下标可能等于
m * n，访问矩阵前必须先进行边界检查。
以后遇到“二维结构整体有序”且复杂度要求为O(log(m * n))的题目，可以优先考虑是否能通过下标映射，把问题转化为标准的一维二分查找。