插值搜索

在二进制搜索算法中，我们总是从数组的中间开始搜索。如果一个数组是均匀分布的，而我们要找的项目可能接近数组的末尾，那么从中间开始搜索对我们来说可能不是一个好的选择。在这种情况下，插值搜索非常有用。插值搜索是对二进制搜索算法的一种改进。插值搜索可以根据搜索键的值进入不同的位置。例如，如果我们正在搜索一个接近数组开头的键，那么它就会搜索到数组的第一部分，而不是从中间开始。位置是通过探针位置计算器公式计算出来的，如下所示：

正如我们所看到的，我们从普通的 mid = (low+high)/2 公式变成了一个看起来更复杂的公式。如果搜索的键值更接近 arr[high]，这个公式将返回一个更高的值，如果键值更接近 arr[low]，这个公式将返回一个更低的值。现在，让我们借助二进制搜索代码来实现这种搜索方法：

在这里，我们采用的是另一种计算方法。虽然计算步骤较多，但好在如果列表是均匀分布的，那么这种算法的平均复杂度为 \$O(log (log n))\$，与二进制搜索的复杂度 \$O(log n)\$ 相比要好得多。此外，如果密钥的分布不均匀，我们也要小心。在这种情况下，插值搜索的性能可能会下降。

现在，我们将探讨二进制搜索的另一种变体，即指数搜索，它可以改进算法。