题目描述
矩阵每行从左到右升序，且每行第一个数都大于上一行最后一个数。判断 target 在不在矩阵里。
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target = 3
输出 = true
思路解析
挨个看当然能找到，可这把「整体有序」这个大礼包完全浪费了，太亏。
既然拉直就是升序数组，那就对 0..m×n−1 这条「虚拟数组」直接二分。要取第 idx 个数时，行号 = idx // n（列数），列号 = idx % n。
lo=0, hi=11：把矩阵拉直就是这条数组。mid=5 对应 matrix[1][1]=11，比 3 大，target 在左边，hi 收到 4。
lo=0, hi=4：mid=2 对应 matrix[0][2]=5，还是比 3 大，继续往左，hi 收到 1。
lo=0, hi=1：mid=0 对应 1，比 3 小，target 在右边，lo 收到 1。
lo=1, hi=1：mid=1 对应 matrix[0][1]=3，正好等于 target。返回 true，全程只看了 4 个数。
看到「每行升序 + 行间衔接」，就把二维拉直当一维，用 idx // n 和 idx % n 来回换算下标，剩下交给二分。
参考代码（Python）
Python
1def searchMatrix(matrix, target):
2 m, n = len(matrix), len(matrix[0])
3 lo, hi = 0, m * n - 1
4 while lo <= hi: # 找具体值，闭区间
5 mid = (lo + hi) // 2
6 v = matrix[mid // n][mid % n] # 一维下标还原行列
7 if v == target: return True
8 elif v < target: lo = mid + 1
9 else: hi = mid - 1
10 return False复杂度分析
- 时间复杂度：O(log(m·n)) —— 在 m·n 个数上二分
- 空间复杂度：O(1) —— 没开额外空间
套路模板
记牢换算公式：行 = mid // n、列 = mid % n，n 是列数。这是全题唯一的坎。
Python
1lo, hi = 0, m * n - 1
2while lo <= hi:
3 mid = (lo + hi) // 2
4 v = matrix[mid // n][mid % n]
5 if v == target: return True
6 elif v < target: lo = mid + 1
7 else: hi = mid - 1易错点
- ❌ mid // m、mid % m（用行数换算） → ✅ mid // n、mid % n（用列数 n）（拉直是按行铺的，每行有 n 个数，所以除、模都用列数 n）
- ❌ hi = m * n（越界） → ✅ hi = m * n - 1（一共 m×n 个数，最大下标是 m×n−1）
- ❌ while lo < hi → ✅ while lo <= hi（这题找的是具体值、不是边界，要用闭区间 lo<=hi，否则会漏判最后一个数）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。