二分查找
在已排序的数组里找值:看中间那个,扔掉值不可能在的那一半。每次比较都让剩下的部分减半。
- 最佳 Ω(1)
- Θ(log n)
- 最差 O(log n)
- 内存 O(1)
log₂ n:n 能对半分多少次才剩 1。64 个值是 6 次,所以最多比较 7 次。
本页的其他术语
- 已排序:按升序排列。二分查找需要这一点;对未排序的数据它会给出错误答案。
- 对半分:每次比较扔掉剩余部分的一半,也就是目标不可能在的那一半。
- 中间 (mid)
- 找到
- 已排除
- 目标
试试看： 选一个不在数组中的目标。查找仍会在 lo 超过 hi 时结束,最多比较 ⌈log₂(n + 1)⌉ 次。
工作原理
二分查找用 lo 和 hi 两个标记圈住目标仍可能存在的范围。它看中间的值:如果就是目标,结束;如果更小,目标只可能在右边,于是 lo 移到中间之后;如果更大,hi 移到中间之前。每一步都让剩余部分减半:64 个值最多比较 7 次,一百万个最多 20 次。当 lo 超过 hi,就什么都不剩了:这个值不在数组中。
适用场合
只要数据已排序并且能直接跳到任意位置,就用二分查找:在有序列表里找单词、在发布历史里找版本、git bisect、在有序数组里找插入位置。对未排序的数据它会给出错误答案,而先排序只有在要查很多次时才划算。