查找 · 单步演示
二分查找
在有序数组里找数：每次看区间正中间的那个，比目标小就丢掉左半边，比目标大就丢掉右半边，区间每一步缩小一半。
30lo
91
142
213
274
355
426
567
618
789hi
步 001 / 009数组已按从小到大排好。查找区间是整个数组 [0..9]。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
lo ← 0；hi ← n−1while lo ≤ himid ← lo + ⌊(hi − lo) / 2⌋if a[mid] = target：return midelse if a[mid] < target：lo ← mid+1else：hi ← mid−1return −1
变量
| target | 42 |
|---|---|
| lo | 0 |
| hi | 9 |
| mid | — |
| 比较次数 | 0 |
复杂度
| 最好情况 | O(1) |
|---|---|
| 平均情况 | O(log n) |
| 最坏情况 | O(log n) |
| 额外空间 | O(1) |
每轮区间至少缩小一半，n 个数最多 ⌊log₂n⌋+1 轮。1,000,000 个数最多只要 20 轮。
要点
- 前提是数组有序，这一点不满足，结果就不可信。
- 循环条件 lo ≤ hi 与 hi ← mid−1 是配套的：区间是闭区间 [lo, hi]。
- 有重复值时返回的是其中某一个位置，不一定是第一个。
常见错误
把 lo ← mid+1 写成 lo ← mid，区间只剩两个数时会原地打转，陷入死循环。