Python語言實(shí)現(xiàn)二分法查找
前言：
二分法也就是二分查找，它是一種效率較高的查找方法
假如公司新來了一個(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ù)則舍棄對(duì)中位數(shù)的前一半查找，反之則舍棄對(duì)后一半范圍查找，達(dá)成開方效果。 步驟3：在新的查找范圍重新計(jì)算出中位數(shù)
步驟4：查找頁碼對(duì)比中位數(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é)：
根據(jù)結(jié)果反饋，使用二分法常規(guī)Python檢索用循環(huán)方式找數(shù)字21，他是排在11位，中位數(shù)查詢3次，使用Python二分法檢索遞歸方式先取查詢數(shù)字的倍數(shù)，然后鎖定前半段進(jìn)行索引,索引的步驟耗時(shí)更少
到此這篇關(guān)于Python語言實(shí)現(xiàn)二分法查找的文章就介紹到這了,更多相關(guān)Python二分法查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Python優(yōu)雅實(shí)現(xiàn)二分查找的示例詳解
- 使用Python實(shí)現(xiàn)二分法查找的示例
- Python實(shí)現(xiàn)二分法查找及優(yōu)化的示例詳解
- Python?二分查找之bisect庫的使用詳解
- Python算法練習(xí)之二分查找算法的實(shí)現(xiàn)
- 詳解Python查找算法的實(shí)現(xiàn)(線性,二分,分塊,插值)
- python二分法查找函數(shù)底值
- python二分法查找實(shí)例代碼
- python中二分查找法的實(shí)現(xiàn)方法
- python實(shí)現(xiàn)二分查找算法
- python二分查找搜索算法的多種實(shí)現(xiàn)方法
相關(guān)文章
這篇文章主要介紹了Python對(duì)象的list如何快速按照屬性查找問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
使用BeautifulSoup爬蟲程序獲取百度搜索結(jié)果的標(biāo)題和url示例
這篇文章主要介紹了使用BeautifulSoup編寫了一段爬蟲程序獲取百度搜索結(jié)果的標(biāo)題和url的示例，大家參考使用吧2014-01-01
Python如何快速實(shí)現(xiàn)分布式任務(wù)
這篇文章主要介紹了Python如何快速實(shí)現(xiàn)分布式任務(wù),小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-07-07
Apache?DophinScheduler定時(shí)調(diào)度Python腳本的實(shí)現(xiàn)
本文主要介紹了Apache?DophinScheduler定時(shí)調(diào)度Python腳本的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
這篇文章主要介紹了Django 大文件下載實(shí)現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08
這篇文章主要介紹了Keras之自定義損失(loss)函數(shù)用法說明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-06-06
這篇文章介紹了Python中的加密與解密模塊hashlib與hmac，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06
Python隨機(jī)生成數(shù)據(jù)后插入到PostgreSQL
本文主要介紹利用python的random庫生成隨機(jī)數(shù)，然后插入到PostgreSQL數(shù)據(jù)庫中，有需要的可以參考學(xué)習(xí)。2016-07-07
這篇文章主要介紹了簡單了解Django View（視圖系統(tǒng)）,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
這篇文章主要為大家介紹了Python 內(nèi)置方法和屬性，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12