Python語言實現二分法查詢

2022-03-14 13:01:49

前言：

二分法也就是二分查詢，它是一種效率較高的查詢方法

假如公司新來了一個人，叫張三，他是你們公司第47個人，過了一段時間後，有些人呢看張三不爽，離職了，那這時候張三肯定不是公司第47個人了，怎麼樣才知道張三排第幾呢，下面我們用二分法把他找出來

思路：

給你一本1000頁的書籍，隨機給定一個頁碼，如何用最快的方式找到它？如果一頁一頁逐步去查詢，則最高需要查詢一千次！那我們如何用二分法來解決這個問題呢？二分法的關鍵就是二分這個詞。

步驟1：設定一個頁碼作為中心點來將1000頁分為兩份，中位數的作用就是每次縮小一半查詢範圍，即達到開方的效果。即可以用 (首位+末位)/2 = 中位數。

步驟2：將需要查詢的頁碼與中位數比價,如果大於中位數則捨棄對中位數的前一半查詢，反之則捨棄對後一半範圍查詢，達成開方效果。步驟3：在新的查詢範圍重新計算出中位數

步驟4：查詢頁碼對比中位數，確定新的查詢範圍

步驟5：迴圈以上步驟，直到找到該頁碼為止

程式碼：

通過以上思路解析,我們知道了二分法實行步驟,接下來就通過程式碼來實現步驟，首先是迴圈實現

#模擬頁碼
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#首位值
low = 0
#末位值
height = len(array)-1
#設定查詢頁碼
findNum = 1
 
#迴圈查詢
while True:
    #獲取中位數
    mid = int((low+height)/2)
    #列印中位數,檢視迴圈次數
    print(array[mid])
    #如果中位數小於查詢值,則鎖定後半段
    if array[mid] < findNum:
        #重置低位數
        low = mid + 1
    #如果中位數大於查詢值,則鎖定前半段
    elif array[mid] > findNum:
        #重置高位值
        height = mid - 1
    #找到數位則列印該值下標,終止迴圈
    elif array[mid]==findNum:
        print('find it:',array[mid],' index:',mid)
        break

除了上述方式外,也可以使用遞回來實現,程式碼更加簡潔

array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
 
#函數遞迴
#定義一個函數,給三個形參:低位值，高位值，查詢值
def BinarySearch(low,height,findNum):
    #計算出中位數
    middle = (low+height)//2
    #如果中位數小於查詢值,則鎖定後半段
    if findNum >array[middle]:
        #重置低位數
        low = middle +1
    #如果中位數大於查詢值,則鎖定前半段
    elif findNum<array[middle]:
        #重置高位值
        height = middle - 1
    else:
        #找到該值並返回
        return '該值下標為:%s,值為:%s'%(middle,array[middle])
    #沒有找到則呼叫自身繼續查詢
    return BinarySearch(low,height,findNum)
 
print(BinarySearch(array[0],len(array)-1,19))

總結：

根據結果反饋，使用二分法常規Python檢索用迴圈方式找數位21，他是排在11位，中位數查詢3次，使用Python二分法檢索遞迴方式先取查詢數位的倍數，然後鎖定前半段進行索引,索引的步驟耗時更少

到此這篇關於Python語言實現二分法查詢的文章就介紹到這了,更多相關Python二分法查詢內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Python語言實現二分法查詢

熱門文章