插值查找是一種改進自二分查找的算法，它通過更智慧型地選擇查找點來提高查找效率。在二分查找中，查找點通常是序列的中間位置，而在插值查找中，查找點是根據要查找的元素與序列中的最大和最小元素之間的關係動態計算的。這種算法特別適用於元素分布均勻的有序序列，在這種情況下，它的查找效率高於二分查找。如果元素分布不均勻，插值查找的性能可能會退化。
插值查找的基本思想是利用公式來預測要查找的元素可能所在的位置，然後從這個位置開始進行查找。這種方法減少了不必要的比較次數，尤其是在數據分布均勻的情況下。
插值查找的公式可以表示為：mid=left+((key-arr[left])/(arr[right]-arr[left]))*(right-left)，其中key是要查找的鍵值，arr[right]和arr[left]是序列中的最大值和最小值。
插值查找的時間複雜度取決於數據的分布情況。在數據分布均勻的情況下，它的平均時間複雜度優於二分查找，可以達到O(log2(log2n))，但在最壞的情況下可能會退化為O(n)。因此，插值查找適用於數據分布均勻的有序序列。