插值查找
插值查找，又名Interpolation Search，是基于有序数列的元素查找，在采用二分查找算法的思想上进行了改进。
其在最小值与最大值范围内，用公式确定中间分割比较点mid。这里，我们具体的插值公式如下所示：
其时间复杂度为：O(loglogN)。
插值查找公式计算
假设，我们的数列还是[1,3,5,7,9,11,13]，我们还是需要查找数值13。那么,根据上面的公式(left=0,right=6)，我们计算得出mid=（13-1）*6/(13-1)=6，这样我们一次就能找到我们需要查找的元素13。
不过，需要注意的是，插值查找适用于元素分布比较均匀的情况，比如博主提供的数组，它们之间间隔仅为2，这就非常的均匀了。
如果不是分布均匀的数列，那么不适合插值查找算法。所以，我们在进行查找一个数据时，需要先分析数列的特点，然后选择合适的算法。
实战：插值查找
话不多说，我们直接通过Python实现查找插值，示例如下：
def Interpolation_search(my_list, key): left = 0 right = len(my_list)-1 while left <= right: mid = left + int((right - left) * (key - my_list[left]) / (my_list[right] - my_list[left])) if key < my_list[mid]: right = mid - 1 elif key > my_list[mid]: left = mid + 1 else: return mid return "None" if __name__ == "__main__": my_list = [1, 3, 5, 7, 9, 11, 13] print("二分查找的原始数列：", my_list) print("二分查找的返回结果：", Interpolation_search(my_list, 13))
运行之后，效果如下：
