搜索二维矩阵
Search a 2D Matrix
在每行有序、且下一行首元素大于上一行末元素的矩阵中查找 target。
在力扣中练习题目描述
给你一个满足下述两条属性的 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-104 <= matrix[i][j], target <= 104
解题思路
主解法
一维二分 · 下标映射
把矩阵按行展开成一个升序数组，直接二分
题目给出的矩阵有一个很强的性质：每行升序，且下一行第一个元素大于上一行最后一个元素。因此把矩阵按行优先展开，就是一个整体升序的一维数组。
在一维下标 [0, m·n-1] 上二分，取出的值用 matrix[mid / n][mid % n] 映射回二维。
分步图解
矩阵 3×4 整体按行优先升序，一维下标 k 对应 matrix[k/n][k%n]。
自拟矩阵 3×4，target 24 的一维下标是 7。二分过程中 mid 依次落在 5、8、6、7，每次都要正确映射行列，不能把 / 和 % 写反。
分步图解
mid=6 映射到 (1,2)，值 21 太小，向右缩；新区间 [7,7]。
- left
- 7
- right
- 7
时间 O(log(m·n))，空间 O(1)。这个技巧只适用于“整体有序”的矩阵；如果只是行列分别有序，应该用第 240 题的阶梯搜索。
时间 O(log(m·n))空间 O(1)
易错点
- 映射写成 matrix[mid % n][mid / n]：行列颠倒。
- 把只满足行列递增的矩阵也这样展开：整体并不有序，二分失效。
- mid 用 (left+right)/2：大矩阵可能溢出。
代码与演示
演示输入
matrix = [[1,4,7,11],[15,18,21,24],[27,30,33,36]]，target = 24矩阵 3×4 整体按行优先升序，一维下标 k 对应 matrix[k/n][k%n]。
查看 C++ 代码
延伸阅读
- 二维下标与一维下标的互换公式是 k = r·n + c，反解是 r=k/n、c=k%n。
- 第 74 题（整体有序）和第 240 题（行列分别有序）看起来相似，但可用算法不同，先确认矩阵性质。