Python数据结构与算法（20）

插值查找 又名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