- 目标
- 仍有可能
- 比较中
- 已排除
- 已找到
指数搜索
指数搜索分两个阶段在有序列表中查找一个值。先依次查看第 1, 2, 4, 8, 16 位,依此类推,每次翻倍,直到那里的值不小于目标。然后对最后两个位置之间的这段范围做二分查找。选择要查找的值,看看为什么靠近开头的目标只需几次比较就能找到。 按“播放”观看查找过程,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到任意位置。虚线标出要查找的值,阴影部分是它仍可能所在的范围。指数搜索需要有序列表,所以未排序的列表会先排序。可选择要查找的值、柱子数量,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择要查找的值和柱子数量。也可以输入自己的数字:指数搜索会先对它们排序。
- 按“播放”,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到查找的任意位置。
- 分别查找一个靠近开头的值和一个靠近末尾的值,把比较次数与“二分查找需要”对比。
指数搜索的原理
查看第 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 — 无需安装,无需信用卡即可启动。
前往编辑器