使用Python實(shí)現(xiàn)二分法查找的示例
關(guān)于二分法的定義我就不說了,CSDN很多大牛和前輩都已經(jīng)闡述的很清楚了,直接上代碼。
首先,先創(chuàng)建一個(gè)名稱為 binary_search 的函數(shù):傳遞兩個(gè)參數(shù),元素列表和要查找的值。
def binary_search(_list, value):
接下來,在函數(shù)內(nèi)部定義所需的變量,二分法的關(guān)鍵在于從列表的中間向兩側(cè)查找(表述可能不嚴(yán)謹(jǐn),大概這個(gè)意思),所以為了直觀起見,定義 left,right, mid 三個(gè)變量,分別代表:列表的起始索引,結(jié)束索引和中間索引。
left = 0 # 列表的起始索引 right = len(_list) # 列表的結(jié)束索引 mid = int((left + right)/2) # 采用此方法,通過四舍五入剛好可以定位到列表的中間位置
接下來是實(shí)現(xiàn)二分查找的關(guān)鍵部分,先定義一個(gè)while循環(huán),使得查找可以順利進(jìn)行,while函數(shù)內(nèi)嵌套 if 分支語句實(shí)現(xiàn)條件判斷,共有三種情況:
1. _list[mid] == value: 中間值恰好是我們需要查找的值,那么直接返回對應(yīng)的索引就可以了。
2. _list[mid] > value: 要查找的值在mid的左側(cè),更新right 的值為mid,縮小查找范圍。
3._list[mid] < value:要查找的值在mid的右側(cè),更新left 的值為mid,到 mid 右側(cè)進(jìn)行查找。
最后,對mid的值做一下更新,以便開始下一輪查找,同時(shí)采用 while-else語句針對沒有查找到的情況進(jìn)行判斷,并給定一個(gè)返回值。
while left < right: if _list[mid] == value: return mid elif _list[mid] > value: right = mid else: left = mid mid = int((right + left)/2) else: return -1
最后,完整代碼,以及測試運(yùn)行表現(xiàn)如下:
""" a demo realize binary search""" def binary_search(_list, value): left = 0 # 列表的起始索引 right = len(_list) # 列表的結(jié)束索引 mid = int((left + right)/2) # 采用此方法,通過四舍五入剛好可以定位到列表的中間位置 while left < right: if _list[mid] == value: return mid elif _list[mid] > value: right = mid else: left = mid mid = int((right + left)/2) else: return -1 index = "the index of value in the list: {}" print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))
運(yùn)行結(jié)果:
沒有要查找的值的情況:
到此這篇關(guān)于使用Python實(shí)現(xiàn)二分法查找的示例的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)二分法查找內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Python優(yōu)雅實(shí)現(xiàn)二分查找的示例詳解
- Python實(shí)現(xiàn)二分法查找及優(yōu)化的示例詳解
- Python?二分查找之bisect庫的使用詳解
- Python算法練習(xí)之二分查找算法的實(shí)現(xiàn)
- 詳解Python查找算法的實(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)文章
Python3合并兩個(gè)有序數(shù)組代碼實(shí)例
這篇文章主要介紹了Python3合并兩個(gè)有序數(shù)組代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08淺析python3字符串格式化format()函數(shù)的簡單用法
這篇文章主要介紹了python3字符串格式化format()函數(shù)的簡單用法,代碼簡單易懂,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-12-12使用Python的SymPy庫解決數(shù)學(xué)運(yùn)算問題的方法
這篇文章主要介紹了使用Python的SymPy庫解決數(shù)學(xué)運(yùn)算問題的方法,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-03-03python網(wǎng)絡(luò)編程學(xué)習(xí)筆記(一)
這篇文章主要介紹了python網(wǎng)絡(luò)編程基礎(chǔ)知識,需要的朋友可以參考下2014-06-06python的數(shù)學(xué)算法函數(shù)及公式用法
在本篇內(nèi)容里小編給大家分享了一篇關(guān)于python的數(shù)學(xué)算法函數(shù)及公式用法,有興趣的朋友們可以參考下。2020-11-11快速了解Python開發(fā)環(huán)境Spyder
這篇文章主要介紹了Python開發(fā)環(huán)境Spyder的的相關(guān)資料,幫助大家更快的上手Spyder,感興趣的朋友可以了解下2020-06-06