学习顺序主线第 05 / 22 课 · 阶段 2

为什么现在学:数组已排好序后,可以利用顺序一次排除一半候选。

返回算法课程
搜索基础

二分查找Binary Search

利用有序性,每次比较中点后排除一半不可能包含答案的区间。

40 分钟前置:数组 · 下标 · 有序性

学完这一课,你应该能做到

  • 说清 [left,right] 保存哪些候选
  • 解释 mid 为什么能被排除
  • 手算不存在的目标,检查循环如何终止

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最直接的办法,为什么慢?

从头到尾逐个比较。

暴力 · O(n)

最多扫描全部 n 个元素,没有利用数组已经有序的信息。

03一步步,推导出优化思路

1

一次比较能告诉我们更多

若中间值小于目标,它左边的全部值也小于目标,可同时排除。

2

维护候选区间

定义闭区间 [left, right]。如果目标存在,它一定还在这个区间内。

3

不断折半直到结束

比较后使用 mid+1 或 mid−1 排除已检查中点。left > right 表示候选区间为空。

贯穿算法的不变量

目标如果存在,始终位于尚未排除的闭区间 [left, right]。

拿一个小输入,逐步手算

在 [1,3,5,7,9] 中找 7,再看找不到 6 时的情况。下方动画默认 target=7。

目标left / rightmid / a[mid]处理
70 / 42 / 55<7,left=3
73 / 43 / 7命中,返回下标 3
6(重新开始)0 / 42 / 55<6,left=3
63 / 43 / 77>6,right=2
63 / 2区间为空停止,返回 -1

目标不存在时,不是因为『循环次数用完』,而是全部候选都已被排除。重复值存在时,本版本返回某个匹配下标,不保证最左或最右。

始终保留目标可能出现的位置

  1. 初始化区间覆盖整个数组;空数组产生 [0,−1],直接结束。
  2. 利用升序性证明被排除区间的每项都不可能匹配,保留下来的区间仍包含所有可能答案。
  3. 每轮命中或至少排除 mid,使候选数严格减少。区间为空时没有答案,返回 -1 正确。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Binary Search交互演示
STEP 01 / 5
二分演示会先升序排列;排序成本另计
1
0
3
1
5
2
7
3
9
4
当前处理已处理 / 已确定未处理
01

前提:数组升序。候选答案在闭区间 [left, right] 内。

binary_search.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

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复杂度,来自具体的工作量

时间复杂度
O(log⁡n)O(\log n)

每轮长度约除以 2。经历 k 轮后约剩 n/2^k 个元素,因此最多进行 O(log₂ n) 轮比较。

辅助空间
O(1)O(1)

迭代实现只保留 left、right、mid 三个下标,不创建随 n 增长的数组。若先排序,排序成本必须另算。

拖动 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这些细节,容易踩坑

01

先明确区间约定

本课采用闭区间,所以 while 是 left <= right。不要和左闭右开模板混用。

02

必须有单调性

未排序数组不能直接二分。实验室为便于观察会先排序,并明确提示。

03

找到不等于找到最左

本算法可返回任何匹配索引。寻找第一个匹配需要在命中后继续收缩右边界。

用反例检查前提

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,仍有一个合法候选。

查看完整推导与答案
  1. 找 4:mid=0,直接命中,返回 0。
  2. 找 2:a[0]>2,所以 right=−1,区间为空,返回 −1。
  3. 若使用 left<right,初始循环不执行,会漏掉目标 4。闭区间的最后一个候选也必须检查。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01为什么可以跳过一整半数组?

02a[mid] < target 时应怎样更新?

03有重复元素时,当前实现保证返回最左索引吗?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。