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