Python查找算法之折半查找算法的實現

一、折半查找算法

折半查找算法又稱為二分查找算法,折半查找算法是將數據分割成兩等份,首先用鍵值(要查找的數據)與中間值進行比較。如果鍵值小於中間值,可確定要查找的鍵值在前半段;如果鍵值大於中間值,可確定要查找的鍵值在後半段。然後對前半段(後半段)進行分割,將其分成兩等份,再對比鍵值。如此循環比較、分割,直到找到數據或者確定數據不存在為止。折半查找的缺點是隻適用於已經初步排序好的數列;優點是查找速度快。

生活中也有類似於折半查找的例子,例如,猜數字遊戲。在遊戲開始之前,首先會給出一定的數字范圍(例如0~100),並在這個范圍內選擇一個數字作為需要被猜的數字。然後讓用戶去猜,並根據用戶猜的數字給出提示(如猜大瞭或猜小瞭)。用戶通常的做法就是先在大范圍內隨意說一個數字,然後提示猜大瞭/猜小瞭,這樣就縮小瞭猜數字的范圍,慢慢地就猜到瞭正確的數字,如下圖所示。這種做法與折半查找法類似,都是通過不斷縮小數字范圍來確定數字,如果每次猜的范圍值都是區間的中間值,就是折半查找算法瞭。

在這裡插入圖片描述

例如,已經有 排序好 的數列:12、45、56、66、77、80、97、101、120,要查找的數據是 101,用折半查找步驟如下:

步驟1:將數據列出來並找到中間值 77,將 101 與 77 進行比較,如下圖所示。

在這裡插入圖片描述

步驟2:將 101 與 77 進行比較,結果是 101 大於 77,說明要查找的數據在數列的右半段。此時不考慮左半段的數據,對在右半段的數據再進行分割,找中間值。這次中間值的位置在 97 和 101 之間,取 97,將 101 與 97 進行比較,如下圖所示。

在這裡插入圖片描述

步驟3:將 101 與 97 進行比較,結果是 101 大於 97,說明要查找的數據在右半段數列中,此時不考慮左半段的數據,再對剩下的數列分割,找中間值,這次中間值位置是 101,將 101 與 101 進行比較,如下圖所示。

在這裡插入圖片描述

步驟4:將 101 與 101 進行比較,所得結果相等,查找完成。說明:如果多次分割之後沒有找到相等的值,表示這個鍵值沒有在這個數列中。

從折半法查找的步驟來看,明顯比順序查找法的次數少,這就是折半查找法的優點:查找速度快。

二、實例:線路故障

有一條的150米線路,在這條線路上存在故障。第一天維修工已經大致鎖定瞭幾個疑似故障點,疑似故障點分別在線路的12、45、56、66、77、80、97、101、120米處。第二天維修工要在這9個疑似故障點中確定一個真正的故障點(假設真正的故障點是101米處)。維修工為瞭快速查找此故障點,就在每段數據的中間位置開始排查。

例如,第一次選擇在77米處的疑似故障點接通電路,發現接通,他判斷此故障在77米之後的位置;第二次取97米處的疑似故障點,發現也接通瞭,說明在97米之後的位置;第三次取101米處的位置,再次接通線路,發現未接通,說明此處是真正的故障點。此次查找經歷瞭3次,將真正故障點找到。具體代碼如下:

def search(data, num):
    """
    定義查找函數:該函數使用的是折半查找算法
    :param data: 原數列data
    :param num: 鍵值num
    :return:
    """
    low = 0  # 定義變量用來表示低位
    high = len(data) - 1  # 定義變量用來表示高位
    print("正在查找.......")  # 提示
    while low <= high and num != -1:
        mid = int((low + high) / 2)  # 取中間位置
        if num < data[mid]:  # 判斷數據是否小於中間值
            # 輸出位置在數列中的左半邊
            print(f"{num} 介於中間故障點 {low + 1}[{data[low]}] 和故障點位置 {mid + 1}[{data[mid]}] 之間,找左半邊......")
            high = mid - 1  # 最高位變成瞭中間位置減1
        elif num > data[mid]:  # 判斷數據是否大於中間值
            # 輸出位置在數列中的右半邊
            print(f"{num} 介於中間故障點 {mid + 1}[{data[mid]}] 和故障點位置 {high + 1}[{data[high]}] 之間,找右半邊......")
            low = mid + 1  # 最低位變成瞭中間位置加1
        else:  # 判斷數據是否等於中間值
            return mid  # 返回中間位置
    return -1  # 自定義函數到此結束


inp_num = 0  # 定義變量,用來輸入鍵值
num_list = [12, 45, 56, 66, 77, 80, 97, 101, 120]  # 定義數列
print("疑似故障點如下:")
for index, ele in enumerate(num_list):
    print(f" {index + 1}[{ele}]", end="")  # 輸出數列
print("")
flag = True  # 開關,用來管控是否多次查找

while flag:  # 循環查找
    inp_num = int(input("請輸入故障點:").strip())  # 輸入查找鍵值
    if inp_num == -1:  # 判斷鍵值是否是-1
        break  # 若為-1,跳出循環 即結束程序
    result = search(num_list, inp_num)  # 調用自定義的查找函數——search()函數
    if result == -1:  # 判斷查找結果是否是-1
        print(f"沒有找到[{inp_num}]故障點")  # 若為-1,提示沒有找到值
    else:
        # 若不為-1,提示查找位置
        print(f"在{result + 1}個位置找到[{num_list[result]}]故障點")
    char = input("本次查找結束,是否繼續查找,請輸入 y(Y) 或 n(N):").strip()
    if char.upper() == "N":
        flag = False

程序執行結果如下圖所示:

在這裡插入圖片描述

到此這篇關於Python查找算法之折半查找算法的實現的文章就介紹到這瞭,更多相關Python 折半查找算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀:

    None Found