插補搜尋 (Interpolation Search)，其實用的就是數學裡內插法的概念來運算。在已排序的資料中，將資料視為線性的解，藉由在線上的移動來尋找我們需要的值。

以上圖的公式 2 為例，當我們用要尋找的值(key)來算出 mid 的時候，比較 mid 是在右半部或是左半部。若是右半部則將 low 的邊界改為 mid，再重複一次圖上的公式 2，反覆運算後直到 mid 等於我們要尋找的值並輸出。反之亦然。

全部的程式碼：

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
def interpolation_search(data, key):
    low = 0
    upper = len(data) - 1
    while low <= upper:
        mid = int((upper - low) * (key - data[low]) / (data[upper] - data[low]) + low)
        if mid < low or mid > upper:
            break
        if key < data[mid]:
            upper = mid - 1
        elif key > data[mid]:
            low = mid + 1
        else:
            return mid

    return -1


index = interpolation_search(data, 6)
if index >= 0:
    print("找到數值於索引 " + str(index))
else:
    print("找不到數值")