本系列文章涉及的演算法包括搜索、回溯、遞回、排序、迭代、貪心、分治和動態規劃等，涉及的資料結構包括字串、串列、指標、區間、佇列、矩陣、堆疊、鏈表、哈希表、線段樹、二叉樹、二叉搜索樹和圖結構等，

本系列文章是筆者為適應當前教育改革的創新要求，更好地踐行語言類課程，滿足實踐教學與創新能力培養的需要，閱讀大量書籍、各大互聯網公司的面試演算法、LintCode、LeetCode、九章演算法和結合筆者近幾年專案經驗撰寫的系列文章，精選了 1000 個趣味性、實用性強的應用實體，從不同難度、不同演算法、不同型別和不同資料結構等方面，將實際演算法進行總結，希望為 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

程式執行結果如下圖所示：

感謝您閱讀本篇博文，希望本文能成為您編程路上的領航者，祝您閱讀愉快！

好書不厭讀百回，熟讀課思子自知，而我想要成為全場最靚的仔，就必須堅持通過學習來獲取更多知識，用知識改變命運，用博客見證成長，用行動證明我在努力，
如果我的博客對你有幫助、如果你喜歡我的博客內容，請 點贊、評論、收藏 一鍵三連哦！聽說點贊的人運氣不會太差，每一天都會元氣滿滿呦！如果實在要白嫖的話，那祝你開心每一天，歡迎常來我博客看看，
?編碼不易，大家的支持就是我堅持下去的動力，點贊后不要忘了 關注 我哦！