Python查找算法之插補查找算法的實現
一、插補查找算法
插補查找算法又稱為插值查找,它是折半查找算法的改進版。插補查找是按照數據的分佈,利用公式預測鍵值所在的位置,快速縮小鍵值所在序列的范圍,慢慢逼近,直到查找到數據為止。根據描述來看,插值查找類似於平常查英文字典的方法。例如,在查一個以字母 D 開頭的英文單詞時,決不會用折半查找法。根據英文詞典的查找順序可知,D 開頭的單詞應該在字典較前的部分,因此可以從字典前部的某處開始查找。鍵值的索引計算,公式如下:
middle=left+(target-data[left])/(data[right]-data[left])*(right-left)
參數說明:
- middle:所求的邊界索引。
- left:最左側數據的索引。
- target:鍵值(目標數據)。
- data[left]:最左側數據值。
- data[right]:最右側數據值。
- right:最右側數據的索引。
例如,已經有排序好的數列:34、53、57、68、72、81、89、93、99。要查找的數據是 53,使用插補查找法步驟如下:
步驟1:將數據列出來並利用公式找到邊界值,計算過程如下:
將各項數據帶入公式:
將數據取整,因此所求索引是 2,對應的數據是 57,將查找目標數據 53 與 57 進行比較,如下圖所示。
步驟2:將 53 與 57 進行比較,結果是 53 小於 57,所以查找 57 的左半邊數據,不用考慮右半邊的數據,索引范圍縮小到 0 和 2 之間,公式帶入:
取整之後索引是 1,對應的數據是 53,將查找目標數據 53 與 53 進行比較,如下圖所示:
步驟3:將 53 與 53 進行比較,所得結果相等,查找完成。說明:如果多次分割之後沒有找到相等的值,表示這個鍵值沒有在這個數列中。
通過上述的步驟1就能看出,插補查找算法比折半查找算法的取值范圍更小,因此它的速度要比折半法查找快,這就是插補查找算法的優點。
二、實例:利用插補查找用戶輸入的數據
用戶可以隨意輸入一組數據,例如本實例輸入一組數據:34、53、57、68、72、81、89、93、99。在這組數據中用插補查找法分別查找數據 57、53、93、89、100,且顯示每次查找的過程。用 Python 代碼實現此過程,具體代碼如下:
def insert_search(data, num): """ 自定義查找函數:該函數使用的是插補查找算法 :param data: 原數列data :param num: 鍵值num :return: """ # 計算 left_index = 0 # 最左側數據的索引 right_index = len(data) - 1 # 最右側數據的索引 print("正在查找.......") # 提示 while left_index <= right_index: # 使用公式計算出索引值 middle = left_index + (num - data[left_index]) / (data[right_index] - data[left_index]) * ( right_index - left_index) # 取整 middle = int(middle) # print(middle) if num == data[middle]: return middle # 如果鍵值等於邊界值,返回邊界位置 elif num < data[middle]: # 輸出位置在數列中的左半邊 print(f"{num} 介於位置{left_index + 1}[{data[left_index]}]和邊界值{middle + 1}[{data[middle]}]之間,找左半邊......") right_index = middle - 1 # 如果鍵值小於邊界值,最右邊數據索引等於邊界位置減1 else: # 輸出位置在數列中的左半邊 print(f"{num} 介於位置{middle + 1}[{data[middle]}]和邊界值{right_index + 1}[{data[right_index]}]之間,找右半邊......") left_index = middle + 1 # 如果鍵值大於邊界值,最左邊數據索引等於邊界位置加1 return -1 # 自定義函數到此結束 inp_num = 0 # 定義變量,用來輸入鍵值 num_list = [34, 53, 57, 68, 72, 81, 89, 93, 99] # 定義數列 print("數據內容是:") for index, ele in enumerate(num_list): print(f" {index + 1}[{ele}]", end="") # 輸出數列 print("") flag = True # 開關,用來管控是否多次查找 while flag: # 循環查找 inp_num = int(input("請輸入要查找的鍵值:").strip()) # 輸入查找鍵值 result = insert_search(num_list, inp_num) # 調用自定義的查找函數——insert_search()函數 if result == -1: # 判斷查找結果是否是-1 print(f"沒有找到[{inp_num}]") # 若為-1,提示沒有找到值 else: # 若不為-1,提示查找位置 print(f"在{result + 1}個位置找到[{inp_num}]") char = input("本次查找結束,是否繼續查找,請輸入 y(Y) 或 n(N):").strip() if char.upper() == "N": flag = False
程序執行結果如下圖所示:
到此這篇關於Python查找算法之插補查找算法的實現的文章就介紹到這瞭,更多相關Python 插補查找算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- None Found