92.搜索二维矩阵
题目
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。
示例 1：
示例 2：
- 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
- 输出：false
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
思路
题目要求 O(log(m·n))，也就是必须二分。
把上面那两条性质连起来看，会发现一件事：
▎ 按行拼接读下来，整个矩阵就是一个完整的升序数组。
1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60
└─第0行──┘ └──第1行───┘ └──第2行────┘
严格升序，一处不乱。第二条性质（行首 > 上行末尾）就是专门为了保证接缝处也递增才给的。
所以这题的本质是：在一个长度为 m·n 的有序数组里二分查找。"二维"只是它的存储方式，不是它的逻辑结构。
注意 O(log(m·n)) 这个复杂度要求本身就在提示你： 它等于 log m + log n，说明目标就是把 m·n 个元素当成一个整体来折半。
既然要当一维数组用，就得能把"第 idx 个元素"翻译成"第几行第几列"。
设列数为 n（每行有 n 个元素），则：
- row = idx / n 整除：跳过了几个完整的行
- col = idx % n 取余：在本行内的偏移
class Solution {
/**
* 搜索二维矩阵 —— 把矩阵当成一维有序数组做二分
*
* 核心思想：题目保证"每行升序 + 行首大于上行末尾"，
* 意味着按行拼接后整个矩阵就是一个完整的升序数组。
* 于是在 [0, m*n - 1] 上二分，取值时用 idx/n、idx%n 换算成坐标。
*
* 时间复杂度 O(log(m * n)) = O(log m + log n)
* 空间复杂度 O(1)：没有真的把矩阵展开成数组
*/
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
// 题目保证矩阵非空，这里仍做一次防御性判断
if (matrix.isEmpty() || matrix[0].isEmpty()) return false
val m = matrix.size
val n = matrix[0].size // 列数，下面换算全靠它
// 闭区间 [left, right]，覆盖全部 m*n 个"虚拟下标"
var left = 0
var right = m * n - 1
while (left <= right) {
// 防溢出写法，别写 (left + right) / 2
val mid = left + (right - left) / 2
// ⚠️ 关键：把一维下标翻译成二维坐标
// 除数和模数都是 n（列数），因为走满 n 个元素才换一行
val value = matrix[mid / n][mid % n]
when {
value == target -> return true // 命中
value < target -> left = mid + 1 // 太小，往右半边找
else -> right = mid - 1 // 太大，往左半边找
}
}
return false // 区间耗尽，不存在
}
}
复杂度
- 时间复杂度: O(log(m * n)) = O(log m + log n)
- 空间复杂度: O(1)没有真的把矩阵展开成数组
- 邮箱 ：charon.chui@gmail.com
- Good Luck!