探查
仍有可能
二分查找需要

  • 目标
  • 仍有可能
  • 比较中
  • 已排除
  • 已找到

更多关于插值查找

插值查找

插值查找在有序列表中找值,就像翻电话簿:找姓“张”的人时,你会翻到靠后的地方,而不是中间。它根据剩余部分两端的值估计目标的位置。选择要查找的值和数值的分布,逐次查看每次探查,看看估计何时胜过二分查找,何时不如。 按“播放”观看查找过程,或用“单步”和“后退”逐步查看。拖动步骤滑块可跳到任意位置。虚线标出要查找的值,阴影部分是它仍可能所在的范围。插值查找需要有序列表,所以未排序的列表会先排序。可选择要查找的值、数值的分布、柱子数量,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择要查找的值、数值的分布和柱子数量。也可以输入自己的数字:插值查找会先将它们排序。
  2. 按“播放”,或用“单步”和“后退”逐步查看。拖动步骤滑块可跳到查找的任意位置。
  3. 将“分布”在“均匀”“随机间隔”和“偏斜”之间切换,比较“探查”和“二分查找需要”。

插值查找的原理

看有序列表中仍可能包含目标的那部分的首值和尾值。比如目标位于首值到尾值的 40% 处,就探查这部分 40% 处的位置。如果那里的值就是目标,查找结束。如果它较小,只剩它之后的位置;如果较大,只剩它之前的位置。在剩余部分中再次估计。如果目标小于首值或大于尾值,它就不在列表中。

估计何时有效

如果数值分布均匀,比如 10, 20, 30 等,第一次估计就会落在目标上或非常接近它,平均约需 log₂(log₂ n) 次探查:十亿个值约需 5 次,而二分查找要 30 次。如果数值扎堆,比如 1, 2, 3, 4, 1000,估计会一再落在错误的位置,每次探查可能只排除一个值,所以最坏情况是 n 次探查。二分查找最多也只需约 log₂ n 次。

常见问题

插值查找是如何工作的?

在有序列表中,它根据剩余部分的首值和尾值估计目标应在的位置,探查该位置,然后只保留正确一侧的部分。它就像二分查找,只是猜测比取中间更聪明。

插值查找比二分查找快吗?

数值分布均匀时是的:平均约需 log₂(log₂ n) 次探查,而不是约 log₂ n 次。数值分布不均匀时,它可能慢得多,最多需要 n 次探查,而二分查找从不超过约 log₂ n 次。

它为什么会很慢?

因为估计假设数值均匀增长。如果大多数值很小,少数值很大,对较小目标的估计会一再落在开头附近,每次只能排除一两个值。

插值查找用在哪里?

用在键接近均匀分布、而探查代价又高的场合,比如在磁盘上按数字 ID 或哈希值查找记录。许多系统把它与二分查找结合,以保证较好的最坏情况。

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

不会。查找在你的浏览器中运行,你最近的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

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

前往编辑器