iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 17
0

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

https://ithelp.ithome.com.tw/upload/images/20181102/20111557F001itiPZ8.jpg

以上圖的公式 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("找不到數值")

上一篇
[演算法] 二分搜尋 (Binary Search)
下一篇
[演算法] 費氏搜尋 (Fibonacci Search)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言