搜索二维矩阵 图解题解
二维矩阵整体有序，和一条升序数组其实是一回事——脑补成数组做二分，行列换算一除一取余，不费吹灰之力。
把矩阵「脑补」成一条拉直的升序数组：每行接着上一行排，整体严格递增。用虚拟下标 0 到 m×n−1 做二分，中点下标除以列数得行号、取余得列号，O(1) 换算回矩阵取真实值——根本不用真的把矩阵拼成数组。每次比一次就砍掉一半范围，log(m×n) 次比较找到答案。
这道题到底在问什么
- matrix
- [[1,3,5,7],[10,11,16,20]]
- target
- 3
- 输出
- true（3 在第 0 行第 1 列）
先想最直接的笨办法
挨个看每个格子当然能找到，可这把「整体有序」这个大礼包完全浪费了。题目都把有序明牌摆你面前了，必须把二分用起来。（动画第 3 步）
最优解：一步一步想明白
- 3挨个看每个格子当然能找到，可这把「整体有序」这个大礼包完全浪费了。题目都把有序明牌摆你面前了，必须把二分用起来。
- 4转折：既然拉直就是升序数组，那就对下标 0..m·n−1 这条「虚拟数组」直接二分。要取第 mid 个数时，行号 = mid // n、列号 = mid % n（n 是列数）。这样根本不用真把矩阵拼起来，O(1) 就能换算回原矩阵取值。
- 5l=0, r=7把矩阵拉直就是这条数组。l=0、r=7，范围是全部 8 个数。要找 target = 3，全程不真拼数组，靠 mid//n、mid%n 回原矩阵取值。
- 6mid = (0+7)//2 = 3中点 mid = (0+7)//2 = 3。换算回矩阵：行 = 3//4 = 0、列 = 3%4 = 3，取到 matrix[0][3] = 7。拿它和 target = 3 比。
- 77 大于 3 → 丢右半7 比 3 大，目标在左半边。把 r 收到 mid−1 = 2，右边那半（含 7，灰）整个丢掉。范围缩到 [0, 2]。
- 8mid = (0+2)//2 = 1现在范围是 [0, 2]。新中点 mid = (0+2)//2 = 1，换算：行 = 1//4 = 0、列 = 1%4 = 1，取到 matrix[0][1] = 3。
- 9matrix[0][1] == 3 ✓matrix[0][1] 正好等于 3！返回 true。全程只看了 2 个数，靠的就是 mid//n、mid%n 这一步换算。
- 104 不在矩阵里换个例子：找 4。数组里没有 4，看二分怎么靠 l 越过 r 收尾。
- 11r → 2mid=3 取到 7，比 4 大，r 收到 2。范围 [0, 2]。
- 12l → 2mid=1 取到 3，比 4 小，l 收到 2。现在 l 和 r 都指向 2。
- 13r → 1，l(2) 大于 r(1) 结束mid=2 取到 5，比 4 大，r 收到 1。这时 l(2) 越过了 r(1)，范围空了，循环结束，返回 false。
- 16看到「每行升序 + 行间衔接」，就把二维拉直当一维，用 mid // n 和 mid % n 来回换算下标，剩下交给二分。这是把高维问题压成一维有序的经典技巧。
⚠️ 容易写错的地方
✗ 错：mid // m、mid % m（拿行数 m 换算）
✓ 对：mid // n、mid % n（拿列数 n 换算）
拉直是按行铺的，每行有 n 个数，所以除、模都用列数 n；用行数 m 会算出完全错的格子
✗ 错：r = m * n（越界）
✓ 对：r = m * n − 1
一共 m×n 个数，最大下标是 m×n−1，写成 m·n 会越界访问
✗ 错：while l ＜ r（漏等号）
✓ 对：while l ＜= r
这题找的是具体值、不是边界，区间缩到只剩一个数时还得比一次，漏等号会漏判最后一个数
完整代码（Python / C++ / Java）
Python
class Solution:
def searchMatrix(self, matrix, target):
m, n = len(matrix), len(matrix[0])
l, r = 0, m * n - 1
while l <= r:
mid = (l + r) // 2
x = matrix[mid // n][mid % n] # 一维下标映射回二维
if x == target: return True
if x < target: l = mid + 1
else: r = mid - 1
return FalseC++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int l = 0, r = m * n - 1;
while (l <= r) {
int mid = (l + r) / 2;
int x = matrix[mid / n][mid % n]; // 映射回二维
if (x == target) return true;
if (x < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
};Java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int l = 0, r = m * n - 1;
while (l <= r) {
int mid = (l + r) / 2;
int x = matrix[mid / n][mid % n]; // 映射回二维
if (x == target) return true;
if (x < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
}套路模板 · 二维矩阵拉直二分（背下来）
l, r = 0, m * n - 1
while l <= r:
mid = (l + r) // 2
v = matrix[mid // n][mid % n] # 行 = mid//n，列 = mid%n
if v == target: return True
elif v < target: l = mid + 1
else: r = mid - 1
return False复杂度
时间复杂度
O(log(m·n))
在 m·n 个数上二分，每轮砍一半
空间复杂度
O(1)
只用 l、r、mid 几个变量，不真拼数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 搜索二维矩阵 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
矩阵整体有序(行内升序 + 行间衔接)，当作长度 m·n 的有序数组二分；下标 mid 映射 matrix[mid//n][mid%n] 取值比较。O(log(m·n))。
和 LC240(行列各自有序但行间不衔接)有何不同？+
LC74 行间衔接、整体有序 → 可整体二分 O(log mn)；LC240 行间不保证有序，用从右上角走的阶梯法 O(m+n)。
复杂度多少？+
二分 log(m·n) 次、每次 O(1) → O(log(m·n))；只用常数变量 O(1)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。