LeetCode 74：搜索二维矩阵——Java 虚拟一维数组与二分查找详解
一、题目描述
给定一个m × n的整数矩阵matrix，矩阵具有以下两个特点：
每一行中的整数从左到右按非严格递增顺序排列；
每一行的第一个整数都大于前一行的最后一个整数。
再给定一个整数target，如果它存在于矩阵中就返回true，否则返回false。
例如：
matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] target = 3数字3位于第一行第二列，因此返回true。如果target = 13，矩阵中不存在该数字，则返回false。
看到“有序”和“查找”这两个关键词，应该优先想到二分查找。本题的关键在于：如何在不创建额外数组的情况下，对二维矩阵进行一次二分查找。
二、为什么可以把矩阵看成一维数组
先观察题目给出的矩阵：
1 3 5 7 10 11 16 20 23 30 34 60每一行内部都是升序的，并且下一行的第一个数字大于上一行的最后一个数字。因此，如果按照从左到右、从上到下的顺序展开，可以得到：
[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]这个一维数组仍然保持整体升序，所以可以直接使用二分查找。
最直观的做法是创建一个新数组，将矩阵中的所有元素复制进去，再对新数组进行搜索。但这会额外占用O(mn)的空间，而且复制数据本身也需要O(mn)的时间。
实际上，我们不需要真正展开矩阵。只要能够把一维数组的下标映射回矩阵中的行和列，就可以把原矩阵当成一个“虚拟的一维数组”。
三、一维下标如何映射到二维坐标
假设矩阵有n列。一维数组中的每n个元素，对应二维矩阵中的一整行。
如果一个元素在虚拟一维数组中的下标为i，那么它在二维矩阵中的坐标为：
行号 = i / n 列号 = i % n这里使用的都是整数运算。
以三行四列的矩阵为例，n = 4：
一维下标
1：行号为1 / 4 = 0，列号为1 % 4 = 1，对应matrix[0][1] = 3；一维下标
6：行号为6 / 4 = 1，列号为6 % 4 = 2，对应matrix[1][2] = 16；一维下标
9：行号为9 / 4 = 2，列号为9 % 4 = 1，对应matrix[2][1] = 30。
因此，在二分查找中得到中间下标mid后，可以直接通过下面的代码访问对应元素：
int num = matrix[mid / n][mid % n];这就是本题最核心的下标映射关系。
可以简单记忆为：
除以列数得到行，模上列数得到列。
四、确定二分查找的边界
矩阵一共有m行、n列，因此元素总数是m × n。如果按照虚拟一维数组处理，其下标范围就是：
0 ～ m × n - 1所以二分查找的左右边界为：
int left = 0; int right = m * n - 1;这里采用闭区间[left, right]。只要left <= right，区间内就仍然存在尚未检查的元素：
while (left <= right) { // 二分查找 }为了避免直接计算(left + right) / 2时发生整数溢出，可以写成：
int mid = left + ((right - left) >>> 1);在本题的数据范围内，截图中的(left + right) >>> 1通常也能通过。但从通用二分查找模板来看，先计算right - left更稳妥。
五、如何更新左右边界
通过映射关系取得中间元素后，将它与target比较：
int num = matrix[mid / n][mid % n];接下来有三种情况。
1. 中间元素等于目标值
if (num == target) { return true; }说明已经找到目标值，可以直接结束搜索。
2. 中间元素小于目标值
if (num < target) { left = mid + 1; }因为虚拟数组整体有序，所以mid及其左侧的元素都不可能等于target，下一轮只需要搜索右半部分。
3. 中间元素大于目标值
else { right = mid - 1; }此时mid及其右侧的元素都可以排除，下一轮只搜索左半部分。
如果循环结束后仍未返回true，说明目标值不存在，最终返回false。
六、完整 Java 代码
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; // 行数 int n = matrix[0].length; // 列数 // 将二维矩阵视为一个虚拟的一维有序数组 int left = 0; int right = m * n - 1; while (left <= right) { // 计算虚拟一维数组的中间下标 int mid = left + ((right - left) >>> 1); // 将一维下标映射回二维矩阵坐标 int num = matrix[mid / n][mid % n]; if (num == target) { return true; } if (num < target) { left = mid + 1; } else { right = mid - 1; } } return false; } }这段代码没有真正创建一维数组，只是在逻辑上将二维矩阵展开。二分查找使用的是虚拟下标，只有访问元素时才通过除法和取模转换为二维坐标。
七、示例推演
仍以如下输入为例：
matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] target = 3矩阵共有3 × 4 = 12个元素，因此初始搜索区间为[0, 11]。
第一次查找：
mid = 5 row = 5 / 4 = 1 col = 5 % 4 = 1 num = matrix[1][1] = 11因为11 > 3，所以令right = 4。
第二次查找：
mid = 2 row = 2 / 4 = 0 col = 2 % 4 = 2 num = matrix[0][2] = 5因为5 > 3，所以令right = 1。
第三次查找：
mid = 0 num = matrix[0][0] = 1因为1 < 3，所以令left = 1。
第四次查找：
mid = 1 num = matrix[0][1] = 3中间元素等于目标值，返回true。
八、复杂度分析
矩阵中共有m × n个元素，二分查找每次都将搜索范围缩小一半，因此时间复杂度为：
O(log(m × n))算法只使用了几个变量，没有创建真正的一维数组，因此空间复杂度为：
O(1)九、常见错误
1. 使用mid / m计算行号
映射时应该除以列数n，因为一维数组中每连续n个元素构成一行。正确写法是：
matrix[mid / n][mid % n]2. 将右边界写成m * n
一共有m × n个元素，但最后一个下标是m × n - 1。闭区间写法中，右边界应为：
int right = m * n - 1;3. 更新边界时没有跳过mid
如果写成left = mid或right = mid，在某些情况下区间无法继续缩小，可能造成死循环。闭区间模板应使用mid + 1和mid - 1。
4. 忽略矩阵整体有序的前提
这种虚拟展开后二分查找的方法成立，是因为下一行首元素大于上一行尾元素。如果只保证每行有序，而不能保证行与行之间整体有序，就不能直接使用本方法。
5. 真的创建一维数组
创建数组虽然也能完成搜索，但会带来O(mn)的复制时间和额外空间，失去了虚拟映射的优势。
十、总结
这道题本质上仍然是一道标准二分查找题。矩阵看起来是二维结构，但题目给出的两条有序条件保证了它按行展开后是一个完整的升序数组。
我们不需要真正展开矩阵，只需在[0, m × n - 1]范围内进行二分查找。当得到一维下标mid后，利用mid / n找到行号，利用mid % n找到列号，再访问对应的矩阵元素。