插值搜索/排序

Question

有人能给我快速浏览一下什么是插值搜索/排序吗？我做了一些搜索，根据我的理解，这意味着你可以根据某物的索引来查找和条目。有人能解释一下这是怎么回事吗？可以用and示例吗？

我相信这非常简单，我只是想得太多了。还有为什么在最坏的情况下。线性时间？谢谢!

Answer 1

插值搜索是二进制搜索的一个更花哨的版本。二分搜索的工作原理是找到一个中间索引，从该索引递归查找目标元素。

如果你正在使用普通的二进制搜索来查找字典，你会在"m“个单词处打开字典，并比较你要查找的单词，然后搜索出现在前面或后面的单词。

插值排序给你一个更好的起点，更精确地匹配人们的搜索方式。如果你在字典中查找单词Aardvark，你不会从M开始，而是从开头开始。

要找到更精确的起始中值插值排序，请使用以下公式计算中值：

m = l + (r - l) * (x * a[l]) / (a[r] - a[l])

其中：

m is the midpoint
a is the array you are searching in
l is the left endpoint (ie 0)
r is the right endpoint (ie length of array)
x is the target element