比较
跳跃步长
线性搜索需要

  • 目标
  • 当前块
  • 比较中
  • 已排除
  • 已找到

更多关于跳跃搜索

跳跃搜索

跳跃搜索介于线性搜索和二分查找之间。它在有序列表中每次跳 m 位,只检查每块的最后一个值,直到遇到最后一个值不小于目标的块,然后从这一块的开头扫描。选择要查找的值和跳跃步长,看看跳跃和扫描各需要多少次比较。 按“播放”观看搜索过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。虚线标出要查找的值,阴影部分是当前块。跳跃搜索需要有序列表,所以未排序的列表会先排序。可选择要查找的值、跳跃步长、柱子数量,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择要查找的值、跳跃步长和柱子数量。也可以输入自己的数字:跳跃搜索会先把它们排序。
  2. 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到搜索的任意位置。
  3. 在 40 根柱子上分别试试跳跃步长 2 和 8,并把比较次数与 √n 时对比。

跳跃搜索的原理

把有序列表分成每块 m 个值。看第一块的最后一个值。如果它小于目标,目标就不可能在这一块里,于是跳到下一块的末尾再看。一旦某块的最后一个值不小于目标,目标就只可能在这一块里:回到块的开头,逐个检查其中的值,直到找到目标或越过它。

选择跳跃步长

有 n 个值时,跳跃最多需要 n/m 次比较,扫描最多需要 m 次。步长小,扫描短但跳跃多;步长大则正好相反。总数 n/m + m 在 m = √n 时最小,约为 2√n 次比较:40 个值时最多 13 次,而线性搜索要 40 次,二分查找要 6 次。跳跃搜索往回走从不超过一块,在数据中向后移动很慢时,这一点很有用。

常见问题

跳跃搜索是怎么工作的?

在有序列表上,它每次向前跳 m 位,检查每块的最后一个值。当这个值不再小于目标时,目标就只可能在这一块里,于是从块的开头扫描这一块。

最佳跳跃步长是多少?

√n,取整。跳跃最多需要 n/m 次比较,扫描最多需要 m 次,两者相等时总和最小,即 m = √n。最坏情况下约需 2√n 次比较。

跳跃搜索比二分查找快吗?

不,二分查找需要的比较更少:约 log₂ n 次,而跳跃搜索约 2√n 次。但在数据中往回走代价很高时,跳跃搜索仍可能更好,因为它只往回退一次,退到某一块的开头。

有重复值时,找到的是哪一个?

第一个。它跳过的每一块都以小于目标的值结尾,所以更前面的块不可能有匹配,而扫描从块的开头开始。

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

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

准备好尝试了吗?

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

前往编辑器