01先从一个问题出发
在按编号排列的书架上找一本书。逐本查看很浪费；查看中间编号，就能决定往哪一半找。
一个具体的例子
在 [2, 5, 8, 12, 16, 23, 38] 中查找 16：先检查 12，排除左半；再检查 23，排除右侧；最后找到 16。
02最直接的办法，为什么慢？
从头到尾逐个比较。
暴力 · O(n)
最多扫描全部 n 个元素，没有利用数组已经有序的信息。
03一步步，推导出优化思路
1
一次比较能告诉我们更多
若中间值小于目标，它左边的全部值也小于目标，可同时排除。
2
维护候选区间
定义闭区间 [left, right]。如果目标存在，它一定还在这个区间内。
3
不断折半直到结束
比较后使用 mid+1 或 mid−1 排除已检查中点。left > right 表示候选区间为空。
贯穿算法的不变量
目标如果存在，始终位于尚未排除的闭区间 [left, right]。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Binary Search交互演示
STEP 01 / 7二分演示会先升序排列；排序成本另计
0
1
2
3
4
5
6
7
当前处理已处理 / 已确定未处理
01
前提：数组升序。候选答案在闭区间 [left, right] 内。
binary_search.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
每轮长度约除以 2。经历 k 轮后约剩 n/2^k 个元素，因此最多进行 O(log₂ n) 轮比较。
辅助空间
迭代实现只保留 left、right、mid 三个下标，不创建随 n 增长的数组。若先排序，排序成本必须另算。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
先明确区间约定
本课采用闭区间，所以 while 是 left <= right。不要和左闭右开模板混用。
02
必须有单调性
未排序数组不能直接二分。实验室为便于观察会先排序，并明确提示。
03
找到不等于找到最左
本算法可返回任何匹配索引。寻找第一个匹配需要在命中后继续收缩右边界。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01为什么可以跳过一整半数组？
02a[mid] < target 时应怎样更新？
03有重复元素时，当前实现保证返回最左索引吗？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。