如何使用Python語言實現二分法查找

這篇文章主要為大家展示了“如何使用Python語言實現二分法查找”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“如何使用Python語言實現二分法查找”這篇文章吧。

前言：

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

假如公司新來了一個人，叫張三，他是你們公司第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語言實現二分法查找”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！