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