跳跃搜索

跳跃搜索就像在没有目录的书里找某一页:一次往后翻一叠,扫一眼页码,一旦翻过头了,就在最后那一叠里往回一页页找。在有序列表上,它需要的比较远少于逐个检查每个值。

一排已排序的柱子分成若干块,每个被跳过的块的最后一根柱子变淡,可能包含目标的块带有阴影
一排已排序的柱子分成若干块,每个被跳过的块的最后一根柱子变淡,可能包含目标的块带有阴影

基本思路

在有序列表中,一块的最后一个值能告诉你目标是否可能在这一块里:如果它小于目标,块中每个值也都小于目标。所以根本不用看块内部。依次检查每块的最后一个值,整块整块地跳过,直到某块的最后一个值不小于目标。这时目标只可能在这一块里:从块的开头扫描。

一个例子

在 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 块的思路常称为平方根分解,也出现在许多其他算法中。

本·施奈德曼(左)与凯瑟琳·普莱桑特在2012年Webshop。施奈德曼于1978年描述了跳跃搜索。
本·施奈德曼(左)与凯瑟琳·普莱桑特在2012年Webshop。施奈德曼于1978年描述了跳跃搜索。

动手试试

打开应用,在“查找”中选择一个值,然后按“单步”。每次跳跃都会突出显示一块的最后一个值;被跳过的块会变淡,可能包含目标的块在扫描时带有阴影。在 40 根柱子上把“跳跃步长”从 √n 改成 2 或 8,看看跳跃和扫描之间的平衡如何变化。

常见问题

跳跃搜索的时间复杂度是多少?

每块 √n 个值时为 O(√n):最多约 2√n 次比较。它只需要 O(1) 的额外内存,但要求列表有序。

跳跃搜索和二分查找有什么区别?

二分查找每次把剩余部分减半,约需 log₂ n 次比较,但会来回移动。跳跃搜索以固定步长向前跳,再扫描一块,约需 2√n 次比较,而且只往回退一次。

最后一块的扫描能改用二分查找吗?

可以。用二分查找搜索这一块,扫描就从 m 次比较减少到约 log₂ m 次。跳跃仍需 n/m 次,所以这时用更大的块更划算。

跳跃搜索需要有序列表吗?

需要。之所以能放心跳过一块,是因为它的最后一个值较小,就意味着块中每个值都较小。应用会先对未排序的列表排序。

准备好尝试了吗?

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

试试跳跃搜索