题目给定一个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))的题目可以优先考虑是否能通过下标映射把问题转化为标准的一维二分查找。