插值查找

在电话簿里找姓“张”的人时,你不会从中间翻开,而是翻到靠后的地方,因为 Z 在字母表中靠后。插值查找对数字也是这样做的。它根据目标的大小猜测它应在的位置,在分布均匀的数据上,这个猜测准得惊人。

一排有序的柱子,一条线从第一根柱子连到最后一根,探查位置落在目标高度与这条线的交点处
一排有序的柱子,一条线从第一根柱子连到最后一根,探查位置落在目标高度与这条线的交点处

基本思路

二分查找无论找什么,总是探查中间。插值查找则利用数值。如果剩余部分从 10 到 100,目标是 70,那么目标位于首值到尾值的三分之二处,所以探查这部分三分之二处的位置。写成公式,探查位置为 lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo)。探查之后,它和二分查找完全一样保留正确一侧的部分,然后再次估计。

两个例子

在 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 中查找 70,第一次就探查第 7 位:1 次探查即找到,而二分查找需要 4 次。再看 1, 2, 3, 4, 5, 6, 7, 8, 9, 999,查找 9。由于有 999,每次估计都落在开头附近:查找依次探查第 1、2、3 位等,一次只前进一位,需要 9 次探查,而二分查找只需 3 次。

有多快

当数值分布均匀,或从均匀分布中随机抽取时,每次探查会把剩余部分从约 n 缩小到约 √n。因此平均约需 log₂(log₂ n) 次探查:即使有十亿个值也只要约 5 次,而二分查找要 30 次。当数值分布非常不均匀时,一次探查可能只排除一个值,最坏情况是 n 次探查,和线性搜索一样差。每次探查还要做一次除法,所以实际上它主要在探查代价高时才划算,比如从磁盘读取。

历史与变体

W. W. Peterson 于 1957 年提出插值查找,用于在随机存取存储设备上查找记录。键均匀分布时平均需要 log log n 次,这一点由 Perl、Itai 和 Avni 于 1978 年证明。实用版本会混入二分步骤来防范不利的数据,例如插值顺序查找或插值二分查找,使最坏情况保持在接近 log n。

动手试试

打开应用,在“查找”中选择一个值,然后按“单步”。每次探查都会说明目标在两端值之间的什么位置,以及由此指向第几位。把“分布”切换到“均匀”,大多数查找一次探查就结束;切换到“偏斜”,探查会在列表开头一步步缓慢前进。最后一个卡片显示二分查找对同一个值需要多少步。

常见问题

插值查找的时间复杂度是多少?

数值分布均匀时平均为 O(log log n),最坏情况为 O(n)。它需要 O(1) 的额外内存和一个有序列表。

插值查找和二分查找有什么区别?

二分查找总是探查剩余部分的中间。插值查找则根据两端的值,探查目标应在的位置。在分布均匀的数值上它好得多,在偏斜的数值上可能差得多。

什么样的数据适合插值查找?

分布相当均匀的有序数字键:间隔很少的连续 ID、定期事件的时间戳或哈希后的键。它适合探查代价高、少量计算代价低的数据。

为什么应用提供不同的分布?

因为分布决定了估计的好坏。均匀的数值让插值查找看起来近乎神奇,偏斜的数值则暴露出它的弱点。把它们与二分查找的次数对比,最能看清何时该用哪种方法。

准备好尝试了吗?

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

试试插值查找