一、折半查找算法

折半查找算法又稱為二分查找算法，折半查找算法是將數(shù)據(jù)分割成兩等份，首先用鍵值(要查找的數(shù)據(jù))與中間值進(jìn)行比較。如果鍵值小于中間值，可確定要查找的鍵值在前半段；如果鍵值大于中間值，可確定要查找的鍵值在后半段。然后對(duì)前半段(后半段)進(jìn)行分割，將其分成兩等份，再對(duì)比鍵值。如此循環(huán)比較、分割，直到找到數(shù)據(jù)或者確定數(shù)據(jù)不存在為止。折半查找的缺點(diǎn)是只適用于已經(jīng)初步排序好的數(shù)列；優(yōu)點(diǎn)是查找速度快。

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

例如，已經(jīng)有 排序好 的數(shù)列：12、45、56、66、77、80、97、101、120，要查找的數(shù)據(jù)是 101，用折半查找步驟如下：

步驟1：將數(shù)據(jù)列出來并找到中間值 77，將 101 與 77 進(jìn)行比較，如下圖所示。

步驟2：將 101 與 77 進(jìn)行比較，結(jié)果是 101 大于 77，說明要查找的數(shù)據(jù)在數(shù)列的右半段。此時(shí)不考慮左半段的數(shù)據(jù)，對(duì)在右半段的數(shù)據(jù)再進(jìn)行分割，找中間值。這次中間值的位置在 97 和 101 之間，取 97，將 101 與 97 進(jìn)行比較，如下圖所示。

步驟3：將 101 與 97 進(jìn)行比較，結(jié)果是 101 大于 97，說明要查找的數(shù)據(jù)在右半段數(shù)列中，此時(shí)不考慮左半段的數(shù)據(jù)，再對(duì)剩下的數(shù)列分割，找中間值，這次中間值位置是 101，將 101 與 101 進(jìn)行比較，如下圖所示。

步驟4：將 101 與 101 進(jìn)行比較，所得結(jié)果相等，查找完成。說明：如果多次分割之后沒有找到相等的值，表示這個(gè)鍵值沒有在這個(gè)數(shù)列中。

從折半法查找的步驟來看，明顯比順序查找法的次數(shù)少，這就是折半查找法的優(yōu)點(diǎn)：查找速度快。

二、實(shí)例：線路故障

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

例如，第一次選擇在77米處的疑似故障點(diǎn)接通電路，發(fā)現(xiàn)接通，他判斷此故障在77米之后的位置；第二次取97米處的疑似故障點(diǎn)，發(fā)現(xiàn)也接通了，說明在97米之后的位置；第三次取101米處的位置，再次接通線路，發(fā)現(xiàn)未接通，說明此處是真正的故障點(diǎn)。此次查找經(jīng)歷了3次，將真正故障點(diǎn)找到。具體代碼如下：

def search(data, num):
    """
    定義查找函數(shù)：該函數(shù)使用的是折半查找算法
    :param data: 原數(shù)列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]:  # 判斷數(shù)據(jù)是否小于中間值
            # 輸出位置在數(shù)列中的左半邊
            print(f"{num} 介于中間故障點(diǎn) {low + 1}[{data[low]}] 和故障點(diǎn)位置 {mid + 1}[{data[mid]}] 之間，找左半邊......")
            high = mid - 1  # 最高位變成了中間位置減1
        elif num > data[mid]:  # 判斷數(shù)據(jù)是否大于中間值
            # 輸出位置在數(shù)列中的右半邊
            print(f"{num} 介于中間故障點(diǎn) {mid + 1}[{data[mid]}] 和故障點(diǎn)位置 {high + 1}[{data[high]}] 之間，找右半邊......")
            low = mid + 1  # 最低位變成了中間位置加1
        else:  # 判斷數(shù)據(jù)是否等于中間值
            return mid  # 返回中間位置
    return -1  # 自定義函數(shù)到此結(jié)束


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

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

程序執(zhí)行結(jié)果如下圖所示：

到此這篇關(guān)于Python查找算法之折半查找算法的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Python 折半查找算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論