Python語言實(shí)現(xiàn)二分法查找

更新時(shí)間：2022年03月14日 09:42:20 作者：五包辣條！

這篇文章主要介紹了Python語言實(shí)現(xiàn)二分法查找，二分法也就是二分查找，它是一種效率較高的查找方法，下文詳細(xì)介紹，需要的小伙伴可以參考一下

前言：

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

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

思路：

給你一本1000頁的書籍，隨機(jī)給定一個(gè)頁碼，如何用最快的方式找到它？如果一頁一頁逐步去查找，則最高需要查找一千次！那我們?nèi)绾斡枚址▉斫鉀Q這個(gè)問題呢？二分法的關(guān)鍵就是二分這個(gè)詞。

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

步驟2：將需要查找的頁碼與中位數(shù)比價(jià),如果大于中位數(shù)則舍棄對中位數(shù)的前一半查找，反之則舍棄對后一半范圍查找，達(dá)成開方效果。步驟3：在新的查找范圍重新計(jì)算出中位數(shù)

步驟4：查找頁碼對比中位數(shù)，確定新的查找范圍

步驟5：循環(huán)以上步驟，直到找到該頁碼為止

代碼：

通過以上思路解析,我們知道了二分法實(shí)行步驟,接下來就通過代碼來實(shí)現(xiàn)步驟，首先是循環(huán)實(shí)現(xiàn)

#模擬頁碼
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
#設(shè)定查找頁碼
findNum = 1
?
#循環(huán)查找
while True:
? ? #獲取中位數(shù)
? ? mid = int((low+height)/2)
? ? #打印中位數(shù),查看循環(huán)次數(shù)
? ? print(array[mid])
? ? #如果中位數(shù)小于查找值,則鎖定后半段
? ? if array[mid] < findNum:
? ? ? ? #重置低位數(shù)
? ? ? ? low = mid + 1
? ? #如果中位數(shù)大于查找值,則鎖定前半段
? ? elif array[mid] > findNum:
? ? ? ? #重置高位值
? ? ? ? height = mid - 1
? ? #找到數(shù)字則打印該值下標(biāo),終止循環(huán)
? ? elif array[mid]==findNum:
? ? ? ? print('find it:',array[mid],' index:',mid)
? ? ? ? break

除了上述方式外,也可以使用遞歸來實(shí)現(xiàn),代碼更加簡潔

array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
?
#函數(shù)遞歸
#定義一個(gè)函數(shù),給三個(gè)形參:低位值，高位值，查找值
def BinarySearch(low,height,findNum):
? ? #計(jì)算出中位數(shù)
? ? middle = (low+height)//2
? ? #如果中位數(shù)小于查找值,則鎖定后半段
? ? if findNum >array[middle]:
? ? ? ? #重置低位數(shù)
? ? ? ? low = middle +1
? ? #如果中位數(shù)大于查找值,則鎖定前半段
? ? elif findNum<array[middle]:
? ? ? ? #重置高位值
? ? ? ? height = middle - 1
? ? else:
? ? ? ? #找到該值并返回
? ? ? ? return '該值下標(biāo)為:%s,值為:%s'%(middle,array[middle])
? ? #沒有找到則調(diào)用自身繼續(xù)查找
? ? return BinarySearch(low,height,findNum)
?
print(BinarySearch(array[0],len(array)-1,19))

總結(jié)：