Python語(yǔ)言實(shí)現(xiàn)二分法查找
前言:
二分法也就是二分查找,它是一種效率較高的查找方法
假如公司新來(lái)了一個(gè)人,叫張三,他是你們公司第47個(gè)人,過(guò)了一段時(shí)間后,有些人呢看張三不爽,離職了,那這時(shí)候張三肯定不是公司第47個(gè)人了,怎么樣才知道張三排第幾呢,下面我們用二分法把他找出來(lái)
思路:
給你一本1000頁(yè)的書籍,隨機(jī)給定一個(gè)頁(yè)碼,如何用最快的方式找到它?如果一頁(yè)一頁(yè)逐步去查找,則最高需要查找一千次!那我們?nèi)绾斡枚址▉?lái)解決這個(gè)問(wèn)題呢?二分法的關(guān)鍵就是二分這個(gè)詞。
步驟1:設(shè)定一個(gè)頁(yè)碼作為中心點(diǎn)來(lái)將1000頁(yè)分為兩份,中位數(shù)的作用就是每次縮小一半查找范圍,即達(dá)到開(kāi)方的效果。即可以用 (首位+末位)/2 = 中位數(shù)。
步驟2:將需要查找的頁(yè)碼與中位數(shù)比價(jià),如果大于中位數(shù)則舍棄對(duì)中位數(shù)的前一半查找,反之則舍棄對(duì)后一半范圍查找,達(dá)成開(kāi)方效果。 步驟3:在新的查找范圍重新計(jì)算出中位數(shù)
步驟4:查找頁(yè)碼對(duì)比中位數(shù),確定新的查找范圍
步驟5:循環(huán)以上步驟,直到找到該頁(yè)碼為止
代碼:
通過(guò)以上思路解析,我們知道了二分法實(shí)行步驟,接下來(lái)就通過(guò)代碼來(lái)實(shí)現(xiàn)步驟,首先是循環(huán)實(shí)現(xiàn)
#模擬頁(yè)碼 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è)定查找頁(yè)碼 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
除了上述方式外,也可以使用遞歸來(lái)實(shí)現(xiàn),代碼更加簡(jiǎ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]) ? ? #沒(méi)有找到則調(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語(yǔ)言實(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庫(kù)的使用詳解
- 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)文章
使用BeautifulSoup爬蟲(chóng)程序獲取百度搜索結(jié)果的標(biāo)題和url示例
這篇文章主要介紹了使用BeautifulSoup編寫了一段爬蟲(chóng)程序獲取百度搜索結(jié)果的標(biāo)題和url的示例,大家參考使用吧2014-01-01Python如何快速實(shí)現(xiàn)分布式任務(wù)
這篇文章主要介紹了Python如何快速實(shí)現(xiàn)分布式任務(wù),小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-07-07Apache?DophinScheduler定時(shí)調(diào)度Python腳本的實(shí)現(xiàn)
本文主要介紹了Apache?DophinScheduler定時(shí)調(diào)度Python腳本的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03Django 大文件下載實(shí)現(xiàn)過(guò)程解析
這篇文章主要介紹了Django 大文件下載實(shí)現(xiàn)過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08Keras之自定義損失(loss)函數(shù)用法說(shuō)明
這篇文章主要介紹了Keras之自定義損失(loss)函數(shù)用法說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-06-06Python隨機(jī)生成數(shù)據(jù)后插入到PostgreSQL
本文主要介紹利用python的random庫(kù)生成隨機(jī)數(shù),然后插入到PostgreSQL數(shù)據(jù)庫(kù)中,有需要的可以參考學(xué)習(xí)。2016-07-07