题目描述
思路解析
一句话答案：LeetCode 74 搜索二维矩阵：整张表首尾接起来是一条升序序列，当成长度 m·n 的有序数组二分，下标 mid 用 ÷n 取行、%n 取列还原，时间 O(log(m·n))、空间 O(1)。
这道题给的矩阵，行和行之间有什么讲究
给一个 m 行 n 列的矩阵，每行升序，且下一行第一个数比上一行最后一个数大。判断 target 在不在里面，要做到 O(log(m·n))。约定用（行号,列号）定位格子、都从 0 数起。题面 6 行 7 列，target=104 得 true，target=87 落在 86 和 89 之间、表里没有，得 false。
逐个格子比一遍、或者逐行二分，为什么都不够快
42 个格子逐个比最坏 42 次，即 O(m·n)，顶不住 O(log(m·n)) 的线。退一步对每行各二分，O(m·log n)，外层仍逐行走 m 趟。题目要把 m 也塞进 log，这两种都差一口气。
为什么整张矩阵能当成一条排好序的长队
关键在那条行间约束：每行内部升序，下一行开头又比上一行结尾大，把每行首尾接起来，整张矩阵就是一条完全升序、中间不回头变小的序列。既然有序，就不必管它折成几行——拉直成一维（下标 0 到 m·n-1）当成有序数组，直接二分即可。
下标砍到中间那格，怎么换回它在第几行第几列
起手 lo=0、hi=m·n-1 两个一维下标，罩住全部 42 个数。每轮取中点 mid（正中间那个下标，mid=(lo+hi)//2），把这下标还原回二维：行 = mid÷n（整除），列 = mid%n（取余），值是 matrix[mid÷n][mid%n]。拿它和 target 比，三种走向：等于就找到；比 target 大就丢右半，hi 收到 mid-1；比它小就丢左半，lo 进到 mid+1。
两个 target 各走一轮 lo、mid、hi
题面这张表 6 行 7 列（下标从 0 起），一维下标换回二维按列数 7 分组：÷7 得行、%7 得列。先找 104：lo=0、hi=41，mid=20 是 matrix[2][6]=62<104，lo 到 21；mid=31 是 matrix[4][3]=95<104，lo 到 32；mid=36 是 matrix[5][1]=110>104，hi 收到 35；mid=33 是 matrix[4][5]=101<104，lo 到 34；mid=34 是 matrix[4][6]=104，命中，返回 true。
再找 87：mid=20 的 62<87，lo 到 21；mid=31 的 95>87，hi 到 30；mid=25 是 matrix[3][4]=77<87，lo 到 26；mid=28 是 matrix[4][0]=86<87，lo 到 29；mid=29 是 matrix[4][1]=89>87，hi 到 28。此时 lo=29 超过 hi=28，范围空了，返回 false。
换算行列时除数用错，满盘跟着挪位
还原下标按列数 n 分组：行用 mid÷n、列用 mid%n。把 n 错写成行数 m，行列全乱，取到的不是那格。时间 O(log(m·n))，每轮范围减半；空间 O(1)，只用几个下标。循环条件要带等号写 lo<=hi，否则 lo、hi 撞到同一格便不再检查、那格恰是 target 就漏掉；范围大时用 lo+(hi-lo)÷2 防 mid 溢出。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句话：二维当一维二分。idx÷列数=行，idx%列数=列——这把 O(m·n) 暴力降到 O(log(m·n))。
先演示「找得到」：target=104。 把矩阵看成一维数组，下标范围 lo=0 .. hi=41（共 42 个数全部存活），开始二分。
取中点 mid=20：行=20÷7=2，列=20%7=6 → matrix[2][6]=62。和 target=104 比一下。
62 < 104：mid 这个数太小，它和它左边（更小的）21 个数全部排除 → 丢掉，lo 进到 21。
取中点 mid=31：行=31÷7=4，列=31%7=3 → matrix[4][3]=95。和 target=104 比一下。
95 < 104：mid 这个数太小，它和它左边（更小的）11 个数全部排除 → 丢掉，lo 进到 32。
取中点 mid=36：行=36÷7=5，列=36%7=1 → matrix[5][1]=110。和 target=104 比一下。
110 > 104：mid 这个数已经太大，它和它右边（更大的）6 个数全部不可能是答案 → 丢掉，hi 收到 35。
取中点 mid=33：行=33÷7=4，列=33%7=5 → matrix[4][5]=101。和 target=104 比一下。
101 < 104：mid 这个数太小，它和它左边（更小的）2 个数全部排除 → 丢掉，lo 进到 34。
取中点 mid=34：行=34÷7=4，列=34%7=6 → matrix[4][6]=104。和 target=104 比一下。
matrix[4][6]=104 正好等于 target=104 ✓ 命中，返回 true。
再演示「找不到」：target=87（它落在 86 和 89 之间，矩阵里没有这个数）。 把矩阵看成一维数组，下标范围 lo=0 .. hi=41（共 42 个数全部存活），开始二分。
取中点 mid=20：行=20÷7=2，列=20%7=6 → matrix[2][6]=62。和 target=87 比一下。
62 < 87：mid 这个数太小，它和它左边（更小的）21 个数全部排除 → 丢掉，lo 进到 21。
取中点 mid=31：行=31÷7=4，列=31%7=3 → matrix[4][3]=95。和 target=87 比一下。
95 > 87：mid 这个数已经太大，它和它右边（更大的）11 个数全部不可能是答案 → 丢掉，hi 收到 30。
取中点 mid=25：行=25÷7=3，列=25%7=4 → matrix[3][4]=77。和 target=87 比一下。
77 < 87：mid 这个数太小，它和它左边（更小的）5 个数全部排除 → 丢掉，lo 进到 26。
取中点 mid=28：行=28÷7=4，列=28%7=0 → matrix[4][0]=86。和 target=87 比一下。
86 < 87：mid 这个数太小，它和它左边（更小的）3 个数全部排除 → 丢掉，lo 进到 29。
取中点 mid=29：行=29÷7=4，列=29%7=1 → matrix[4][1]=89。和 target=87 比一下。
89 > 87：mid 这个数已经太大，它和它右边（更大的）2 个数全部不可能是答案 → 丢掉，hi 收到 28。
搜索范围空了（lo=29 > hi=28），整张矩阵都比对过、没有等于 target=87 的数 → 返回 false。
越界目标会被二分自然排空，不用特判。
LC74 能整体二分，全靠那条「行间也接得上」的强约束；LC240 没有它，得换 Z 字搜索。
参考代码
def searchMatrix(matrix, target): m, n = len(matrix), len(matrix[0]) lo, hi = 0, m * n - 1 while lo <= hi: mid = (lo + hi) // 2 v = matrix[mid // n][mid % n] # 下标还原成行列 if v == target: return True elif v > target: hi = mid - 1 # 丢右半 else: lo = mid + 1 # 丢左半 return False复杂度
- 时间：O(log(m·n))，对长度 m·n 的有序序列二分，每次范围减半
- 空间：O(1)，只用 lo / hi / mid 几个变量，原地查找
易错点
面试追问把动画讲成自己的话
追问为什么这个矩阵能当一维有序数组，普通排好序的每行矩阵不行？
追问如果改成 LC240（每行每列升序但行间无此强约束）还能这样二分吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
爱吃香蕉的珂珂
LeetCode 875 · 中等 · 沿着 二分查找 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题