比较
仍有可能
二分查找需要

  • 目标
  • 仍有可能
  • 比较中
  • 已排除
  • 已找到

更多关于指数搜索

指数搜索

指数搜索分两个阶段在有序列表中查找一个值。先依次查看第 1, 2, 4, 8, 16 位,依此类推,每次翻倍,直到那里的值不小于目标。然后对最后两个位置之间的这段范围做二分查找。选择要查找的值,看看为什么靠近开头的目标只需几次比较就能找到。 按“播放”观看查找过程,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到任意位置。虚线标出要查找的值,阴影部分是它仍可能所在的范围。指数搜索需要有序列表,所以未排序的列表会先排序。可选择要查找的值、柱子数量,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择要查找的值和柱子数量。也可以输入自己的数字:指数搜索会先对它们排序。
  2. 按“播放”,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到查找的任意位置。
  3. 分别查找一个靠近开头的值和一个靠近末尾的值,把比较次数与“二分查找需要”对比。

指数搜索的原理

查看第 1 位的值。如果它小于目标,就查看第 2 位,然后是第 4, 8, 16 位,每次翻倍。一旦某个值不小于目标就停下:目标只可能在上一个查看的位置之后、这个位置之前。对这段范围做二分查找。如果翻倍超出了列表末尾,就从最后查看的位置到末尾做二分查找。

开头附近很快,且无需知道长度

要到达第 i 位的目标,翻倍阶段约需查看 log₂ i 次,找到的范围内少于 i 个值,所以二分查找还需约 log₂ i 次。总共约 2 log₂ i 次,取决于目标在哪里,而不是列表有多长。靠近开头的目标比普通二分查找找得更快;靠近末尾的目标最多约多花一倍。由于从不需要列表长度,它也适用于长得无法测量或没有已知末尾的列表。

常见问题

指数搜索是如何工作的?

在有序列表上,它依次检查第 1, 2, 4, 8 位,依此类推,直到那里的值不小于目标。这时目标只可能在最后检查的两个位置之间,对这段范围做二分查找即可找到。

指数搜索比二分查找快吗?

目标靠近列表开头时,是的:对于第 i 位的目标,无论列表多长,约需 2 log₂ i 次比较。目标靠近末尾时,普通二分查找更快,最多快约一倍。

它有什么用途?

查找长度未知或无界的列表,例如数据流或无限序列;以及合并有序段,此时下一个匹配通常就在附近。Timsort 的飞奔模式(galloping)也用了同样的翻倍思路。

为什么叫“指数”搜索?

因为它检查的位置呈指数增长:1, 2, 4, 8, 16,每个都是前一个的两倍。它也叫倍增搜索或飞奔搜索。

我的数字会被发送到别处吗?

不会。查找在你的浏览器中运行,上次的设置保存在本浏览器的本地存储中。

准备好尝试了吗?

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

前往编辑器