python 插值查找

插值查找是一种基于有序列表的查找算法，可以在较快的时间内找到目标元素。它与二分查找类似，但是在确定比较位置时使用了插值来计算。

插值查找的基本思想是根据目标元素的估计位置，将查找范围逐渐缩小。具体步骤如下：

1. 确定查找范围的上下界，通常是列表的首尾元素。
2. 根据目标元素的估计位置，计算出一个插值索引。这个插值索引公式可以是 `(目标元素 - 列表的首元素) / (列表的尾元素 - 列表的首元素)`。
3. 比较插值索引处的元素与目标元素的大小关系：
- 如果插值索引处的元素等于目标元素，则查找成功。
- 如果插值索引处的元素大于目标元素，则在插值索引的左侧继续查找。
- 如果插值索引处的元素小于目标元素，则在插值索引的右侧继续查找。
4. 重复步骤 2 和步骤 3，直到找到目标元素或者查找范围为空。

插值查找的时间复杂度为 O(log(log(n)))，相对于二分查找来说，它对于数据分布较为均匀的列表可以更快地找到目标元素。但是，对于数据分布不均匀的列表，插值查找的性能可能会比较差。