插值查找

插值查找是对折半查找的一种优化，但是它的适用场景也比折半查找更狭窄，要求查找表不仅是已经排好序的，而且呈均匀分布。例如英文字母表的排序就是递增均匀分布的，如果我们想要查找某一个单词，如“zero”，那么会下意识的在字典的后半部分翻找。因为字母表是递增均匀分布的，而z字母在字母表中靠后的位置出现。

​ 已知单词会在字典后半部分出现，因此不必再先从中间折半。在此基础上，对折半查找进行了优化，诞生了插值查找，也叫按比例查找。该查找是按照一定比例去修改每次分割的值，所以只需在折半查找的基础上，修改mid的值。

​ 在折半查找中，mid = (begin+last)/2，而在插值查找中，如果要查找的关键字为key，则mid = begin+(key-arr[begin]) *(last-begin)/(arr[last]-arr[gegin])；而其它代码实现与折半查找相同。它在查找之前首先使关键字key与查找表中最大最小记录的关键字比较。

​ 从时间复杂度来看，它也是O(log2n)，但对于较大而且关键字分布又比较均匀的表，插值查找算法的平均性能比折半查找要好得多。注意：如果查找表数据不是均匀分布，用插值查找未必合适。