01先从一个问题出发
在按编号排列的书架上找一本书。逐本查看很浪费;查看中间编号,就能决定往哪一半找。
在 [1,3,5,7,9] 中找 7,再看找不到 6 时的情况。下方动画默认 target=7。
一次比较为什么能排除一半
在有序数组 [1,3,5,7,9] 中找 7。先看中点下标 2,值是 5。我们不只是知道『5 不是 7』:还知道它左边所有值都≤5,也都不可能是 7。所以可以一次排除下标 0、1、2,只保留右边。
如果中点值大于目标,就对称地排除中点及其右边。省掉的工作来自有序性提供的信息,而不是计算中点这个动作本身。无序数组无法做同样的推断。
先固定区间约定,再记代码
本课用闭区间 [left,right],两端都仍可能是答案。因此初始 right=n−1;left=right 时还剩一个候选,必须继续检查,循环条件是 left≤right。
当 a[mid]<target,mid 已确认不等于目标,所以更新为 left=mid+1;若仅写 left=mid,在两个元素的区间中可能反复得到同一个 mid,范围不再缩小。其他二分模板可能使用半开区间,但对应的初始化、循环条件和更新必须一起改变。
02最直接的办法,为什么慢?
从头到尾逐个比较。
最多扫描全部 n 个元素,没有利用数组已经有序的信息。
03一步步,推导出优化思路
一次比较能告诉我们更多
若中间值小于目标,它左边的全部值也小于目标,可同时排除。
维护候选区间
定义闭区间 [left, right]。如果目标存在,它一定还在这个区间内。
不断折半直到结束
比较后使用 mid+1 或 mid−1 排除已检查中点。left > right 表示候选区间为空。
目标如果存在,始终位于尚未排除的闭区间 [left, right]。
拿一个小输入,逐步手算
在 [1,3,5,7,9] 中找 7,再看找不到 6 时的情况。下方动画默认 target=7。
| 目标 | left / right | mid / a[mid] | 处理 |
|---|---|---|---|
| 7 | 0 / 4 | 2 / 5 | 5<7,left=3 |
| 7 | 3 / 4 | 3 / 7 | 命中,返回下标 3 |
| 6(重新开始) | 0 / 4 | 2 / 5 | 5<6,left=3 |
| 6 | 3 / 4 | 3 / 7 | 7>6,right=2 |
| 6 | 3 / 2 | 区间为空 | 停止,返回 -1 |
目标不存在时,不是因为『循环次数用完』,而是全部候选都已被排除。重复值存在时,本版本返回某个匹配下标,不保证最左或最右。
始终保留目标可能出现的位置
- 初始化区间覆盖整个数组;空数组产生 [0,−1],直接结束。
- 利用升序性证明被排除区间的每项都不可能匹配,保留下来的区间仍包含所有可能答案。
- 每轮命中或至少排除 mid,使候选数严格减少。区间为空时没有答案,返回 -1 正确。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
前提:数组升序。候选答案在闭区间 [left, right] 内。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
left, right = 0, len(a) - 1- 闭区间右端是最后一个合法下标。长度为 0 时 right=−1,不要提前读取 a[0]。
mid = left + (right - left) // 2- 取靠左的中点。在固定宽度整数语言中,这种写法还可避免 left+right 溢出;Python 整数没有同样的固定宽度限制。
left = mid + 1- 中点已检查过且过小,所以不能继续留在候选范围。
return -1- 写在循环外。不能只比较一次就断言不存在,也不能返回一个未经检查的 left 当作匹配下标。
05复杂度,来自具体的工作量
每轮长度约除以 2。经历 k 轮后约剩 n/2^k 个元素,因此最多进行 O(log₂ n) 轮比较。
迭代实现只保留 left、right、mid 三个下标,不创建随 n 增长的数组。若先排序,排序成本必须另算。
把工作量具体数出来
候选规模至多按 n、n/2、n/4…缩小。缩到 1 需要约 log₂n 次,时间 O(log n)。n=8 最多可能需要 4 次元素检查,『log₂8=3』统计的是减半次数,不应混淆。
迭代版本只存几个下标,辅助空间 O(1);递归版本还要考虑 O(log n) 调用栈。
如果输入原本无序且只查询一次,先排序再二分通常需要 O(n log n),未必优于 O(n) 的一次扫描。大量查询才更容易摊薄排序成本。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
先明确区间约定
本课采用闭区间,所以 while 是 left <= right。不要和左闭右开模板混用。
必须有单调性
未排序数组不能直接二分。实验室为便于观察会先排序,并明确提示。
找到不等于找到最左
本算法可返回任何匹配索引。寻找第一个匹配需要在命中后继续收缩右边界。
left=mid 会卡在同一个区间
a=[1,3],target=3。left=0、right=1、mid=0。若把 left 更新成 mid,left 仍为 0,下一轮状态完全一样。
怎样修正:已经排除 mid 就移动到 mid+1;同时用空数组、单元素、两元素、目标不存在和重复值验证边界。
08把想法带进真实题目
单元素是最好的边界检查
在 [4] 中分别找 4 和 2。写出第一次 mid、更新后的边界及返回值。如果循环条件改为 left<right,会错在哪里?
需要一点提示
初始 left=right=0,仍有一个合法候选。
查看完整推导与答案
- 找 4:mid=0,直接命中,返回 0。
- 找 2:a[0]>2,所以 right=−1,区间为空,返回 −1。
- 若使用 left<right,初始循环不执行,会漏掉目标 4。闭区间的最后一个候选也必须检查。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01为什么可以跳过一整半数组?
02a[mid] < target 时应怎样更新?
03有重复元素时,当前实现保证返回最左索引吗?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。