基本思路
在有序列表中,一块的最后一个值能告诉你目标是否可能在这一块里:如果它小于目标,块中每个值也都小于目标。所以根本不用看块内部。依次检查每块的最后一个值,整块整块地跳过,直到某块的最后一个值不小于目标。这时目标只可能在这一块里:从块的开头扫描。
一个例子
在 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 中查找 23,每块 3 个值。第一块以 8 结尾,比 23 小,跳过。第二块以 23 结尾,不比它小,所以 23 只可能在 12, 16, 23 中。扫描这一块,依次看到 12、16,然后是 23:经过 5 次比较找到,而线性搜索需要 6 次,二分查找需要 3 次。如果查找 40,块尾 8、23 和 72 指向块 38, 56, 72;38 较小,56 已经较大,所以 40 不在其中:同样是 5 次比较。
为什么是 √n
每块 m 个值时,找到正确的块最多约需 n/m 次比较,扫描它最多需要 m 次。跳得少而远,扫描就长;跳得多而近,跳跃就长。总和 n/m + m 在两部分相等时最小,即 m = √n,此时约为 2√n。40 个值时,每块 6 个,最多 13 次比较;一百万个值时,每块 1,000 个,约 2,000 次比较。
适用场景
二分查找需要的比较更少,约 log₂ n 次。但二分查找在整个列表中来回跳,而跳跃搜索只向前移动,只往回退一次,退到某一块的开头。因此它很适合存放在磁带上或链式结构中、往回走很慢的数据。Ben Shneiderman 在 1978 年以“jump searching”之名描述了这种方法。同样把数据分成 √n 块的思路常称为平方根分解,也出现在许多其他算法中。
动手试试
打开应用,在“查找”中选择一个值,然后按“单步”。每次跳跃都会突出显示一块的最后一个值;被跳过的块会变淡,可能包含目标的块在扫描时带有阴影。在 40 根柱子上把“跳跃步长”从 √n 改成 2 或 8,看看跳跃和扫描之间的平衡如何变化。
常见问题
跳跃搜索的时间复杂度是多少?
每块 √n 个值时为 O(√n):最多约 2√n 次比较。它只需要 O(1) 的额外内存,但要求列表有序。
跳跃搜索和二分查找有什么区别?
二分查找每次把剩余部分减半,约需 log₂ n 次比较,但会来回移动。跳跃搜索以固定步长向前跳,再扫描一块,约需 2√n 次比较,而且只往回退一次。
最后一块的扫描能改用二分查找吗?
可以。用二分查找搜索这一块,扫描就从 m 次比较减少到约 log₂ m 次。跳跃仍需 n/m 次,所以这时用更大的块更划算。
跳跃搜索需要有序列表吗?
需要。之所以能放心跳过一块,是因为它的最后一个值较小,就意味着块中每个值都较小。应用会先对未排序的列表排序。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试跳跃搜索