指数搜索

二分查找要先知道列表在哪里结束,才能查看中间。指数搜索不需要:它以越来越大的步子向前飞奔,直到越过目标,再对最后一步做二分查找。因此它非常适合长度未知的列表,查找靠近开头的值也很快。

一排有序的柱子,上方是长度逐次翻倍的跳跃,经过第 1, 2, 4, 8 位,最后两次跳跃之间的范围带有阴影
一排有序的柱子,上方是长度逐次翻倍的跳跃,经过第 1, 2, 4, 8 位,最后两次跳跃之间的范围带有阴影

基本思路

检查第 1 位的值,然后是第 2, 4, 8, 16 位,依此类推,每个位置都是前一个的两倍。只要那里的值小于目标,目标就一定在更后面。一旦某个值不小于目标,目标就被困住了:它在上一个检查的位置之后,且不晚于这个位置。这段范围是有序的,所以二分查找就能找到目标,或者证明它不存在。

一个例子

在 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 中查找 23。第 1 位是 2,第 2 位是 5,第 4 位是 12,都比 23 小。第 8 位是 56,比 23 大,所以 23 只可能在第 5 到第 7 位。二分查找检查其中间的第 6 位,找到 23:共 5 次比较,而普通二分查找需要 3 次。在同一列表中查找 12,3 次比较后停在第 4 位,比二分查找少一次;查找 2 则在第 1 位只需一次比较就能找到。

比较次数

对于第 i 位的目标,翻倍约 log₂ i 步后停止,留下少于 i 个位置的范围,二分查找再约 log₂ i 次就能覆盖。所以无论列表多长,查找约需 2 log₂ i 次比较。目标靠近开头时,这比二分查找好,后者总是约需 log₂ n 次。目标靠近末尾时,指数搜索最多约多花一倍。对 40 个值,应用中前五个位置平均约需 3 次比较,后五个约需 9 次,而二分查找约为 4.6 次。

长度未知与飞奔模式

Jon Bentley 和 Andrew Yao 在 1976 年为无界搜索提出了这种翻倍策略:在没有已知末尾的有序序列中查找一个值,例如无限列表,或只能逐个位置探查的数据流。同样的思路也能加快合并。当两个有序段中的一个持续胜出时,Timsort 会切换到飞奔模式(galloping):它在另一个有序段中向前查看 1, 2, 4, 8 个位置,找出下一个值该放在哪里,而不是一次只前进一个位置。

动手试试

打开应用,在“查找”中选择一个值,然后按“单步”。每次查看第 1, 2, 4, 8 位等位置时都会高亮;一旦某个值不小于目标,最后两个位置之间的范围就会加上阴影,由二分查找接手。先查找一个较小的值,再查找一个较大的值,把比较次数与二分查找卡片对比。

常见问题

指数搜索的时间复杂度是多少?

对于第 i 位的目标为 O(log i),所以对 n 个值的列表最多为 O(log n)。它需要 O(1) 的额外内存和一个有序列表。

指数搜索和二分查找有什么区别?

二分查找从整个列表开始,需要知道列表长度。指数搜索先通过翻倍找到包含目标的一段范围,再只对这段范围做二分查找。目标靠近开头时它更快,而且不需要知道长度。

为什么把步长翻倍,而不是每次加一个固定值?

每次加固定步长就是跳跃搜索,跨越整个列表约需查看 n 除以步长次。翻倍只需约 log₂ i 次就能到达第 i 位,而且留下的范围最多只比需要的大一倍,所以之后的二分查找依然很短。

指数搜索用在哪里?

用于查找无界或很长的有序数据、合并有序段(Timsort 中的飞奔模式),以及在不知道上限时找出某个条件第一次成立的位置。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试指数搜索