插值搜索收敛的速度有多快？

在排序数组中搜索时，标准方法是依赖二进制搜索。如果输入数组包含N个元素，则在对已排序数组进行log（N）+ 1次随机查询后，您将找到要查找的值。该算法是众所周知的，即使是孩子也是如此。您首先要猜测该值在中间，然后检查该值在中间，然后将其与目标进行比较，然后根据比较结果转到数组下半部分的上半部分。

二进制搜索仅要求对值进行排序。如果这些值不仅被排序，而且还遵循规则的分布，该怎么办。也许您正在生成均匀分布的随机值。也许您正在使用哈希值。

在经典论文中，Perl等人。描述了一种称为插值搜索的可能更有效的方法。当您知道数据的分布时，它适用。直觉很简单：您无需猜测目标值在范围的中间，而是根据该值调整猜测。如果该值小于平均值，则将目标对准数组的开头。如果该值比平均值大得多，您可能会认为索引应该在末尾。

这样，预期的搜索时间就会好得多：log（log（N））。为了获得一些直觉，我快速地在C ++中实现了插值搜索，并进行了一个小实验，生成大型数组并使用插值搜索在其中搜索。如您所见，当您将数组的大小乘以10时，命中或比较的次数几乎保持不变。此外，插值搜索可能会很快非常接近目标。因此，如果内存局部性是一个因素，结果将比其看起来更好。

您可能会反对这样的结果劣于哈希表，并且我确实希望实现良好的哈希表性能更好，但是您应该注意，许多哈希表实现会以提高内存使用为代价来获得性能，并且它们经常失去了以高速顺序访问值的能力。

话虽这么说，我不知道插值搜索在当今的软件中实际上已经被有效地使用。如果您提及这种文物，请分享！