Binary Search
二分查找
~ 11 min · v111
二分查找
cs-algo/binary-search · COMP25211 先玩一局：1–100，你几次能猜到我心里的数？
规则：我心里有个 1–100 的数，你来猜，我只回答"大了 / 小了"。最省的猜法不是从 1 数起，而是每次猜区间正中间——一猜就砍掉一半。下面把这套玩法搬到一个有序数组上：点「下一步」，看三根指针 lo / mid / hi 怎么把范围一刀刀砍到只剩目标。
动手：在有序数组里找一个数
你刚用的就是二分查找：在已经排好序的数组里，每次看中间那个，比一下就砍掉一半范围。lo / hi 框住"还可能藏着目标的区间"，mid 是中点。
唯一前提：数据必须有序——"大了 / 小了"只有在有序时才成立；无序数组用二分会漏掉明明存在的元素。
2 凭什么这么快：每比一次，砍掉一半
回到上面的演示——盯着那个「比较次数」：15 个元素最多 4 次就到底，因为每比一次候选数量就减半（15 → 7 → 3 → 1）。这就是 O(log n) 的含义。
每多允许一次比较，能搞定的规模就翻一倍。所以 10 亿 个有序数，二分也只要约 30 次比较就能定位——而从头线性扫最坏要 10 亿次。
| 查找方式 | 时间（最坏） | 是否需有序 | n=10⁶ 大约比较次数 |
|---|---|---|---|
| 线性查找 linear | O(n) | 否 | 1,000,000 |
| 二分查找 binary | O(log n) | 是 | 20 |
代价就是那个前提：得先有序。所以「只查一次」用线性 O(n) 就够；「反复查很多次」才值得先花 O(n log n) 排好序、之后每次 O(log n) 二分。
3 三个一写就翻车的坑（点一下看）
二分代码就十行，却是出了名的难写对——这三个坑几乎人人踩过。点卡片，下面控制台模拟运行结果。把这一节看懂，胜过背"核心要点"。
4 自测
用上面那个 15 元素数组（2 5 8 12 16 23 38 56 72 73 88 91 94 97 99）想一遍，再点选项对答案。
读完这节，你应该明白：
二分查找＝在有序数组里每次砍一半。三根指针 lo/hi 框住"还可能藏着目标的区间"，mid 是中点；比一次就丢掉一半，所以是 O(log n)。三件保命的事：必须有序、mid=lo+(hi-lo)/2 防溢出、更新用 mid±1 保证区间一定缩小（否则死循环）。把"找下标"换成"找第一个 ≥ target 的位置"，就是 lower_bound——后面学 BST 时，你会发现 BST 查找本质就是把这套二分长在了树上 ↓