日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Python語言實現二分法查找_python

作者：五包辣條！ ? 更新時間： 2022-05-15 編程語言

前言：

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

假如公司新來了一個人，叫張三，他是你們公司第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

總結：

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

原文鏈接：https://blog.csdn.net/AI19970205/article/details/123464424

欄目分類
最近更新