一、折半查找算法
折半查找算法又稱為二分查找算法，折半查找算法是將數據分割成兩等份，首先用鍵值(要查找的數據)與中間值進行比較。如果鍵值小于中間值，可確定要查找的鍵值在前半段；如果鍵值大于中間值，可確定要查找的鍵值在后半段。然后對前半段(后半段)進行分割，將其分成兩等份，再對比鍵值。如此循環比較、分割，直到找到數據或者確定數據不存在為止。折半查找的缺點是只適用于已經初步排序好的數列；優點是查找速度快。
生活中也有類似于折半查找的例子，例如，猜數字游戲。在游戲開始之前，首先會給出一定的數字范圍(例如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 折半查找算法內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- python實現線性回歸算法
- Python實現七大查找算法的示例代碼
- Python查找算法之插補查找算法的實現
- python高效的素數判斷算法
- python實現ROA算子邊緣檢測算法
- Python實現粒子群算法的示例
- Python實現隨機爬山算法
- python中K-means算法基礎知識點
- python 圖像增強算法實現詳解
- python入門之算法學習
