Pythonic版二分查找實(shí)現(xiàn)過程原理解析
前提：升序數(shù)組，待查元素在數(shù)組中。
二分查找：就是一個(gè)遞歸函數(shù)c。待查元素a，當(dāng)前數(shù)組中位數(shù)b，如果b=a則返回b的索引，b>a則在b左側(cè)的子數(shù)組中調(diào)用函數(shù)c，否則在b右側(cè)子數(shù)組中調(diào)用函數(shù)c。
第一次思考，按著上面的思路編程后的結(jié)果：
def binary_search(index, a, value):
if a[(len(a) - 1) // 2] == value:
return index + (len(a) - 1) // 2
elif a[(len(a) - 1) // 2] < value:
return binary_search(index + (len(a) - 1) // 2 + 1, a[(len(a) - 1) // 2 + 1:], value)
else:
return binary_search(index, a[0:(len(a) - 1) // 2 + 1], value)
第二次思考，簡化中位數(shù)計(jì)算邏輯：
def binary_search(index, a, value):
if a[len(a) // 2] == value:
return index + len(a) // 2
elif a[len(a) // 2] < value:
return binary_search(index + len(a) // 2, a[len(a) // 2:], value)
else:
return binary_search(index, a[0:len(a) // 2], value)
第三次思考，去掉return，改為lambda形式：
binary_search = lambda index,a,value: index + len(a) // 2 if a[len(a) // 2] == value else binary_search(index + len(a) // 2, a[len(a) // 2:], value) if a[len(a) // 2] < value else binary_search(index, a[0:len(a) // 2], value)
以上就是二分查找變?yōu)椤耙恍写a”版的過程。
運(yùn)行測試：
if __name__ == '__main__':
a = [1, 2, 33, 43, 52, 66, 88, 99, 111, 120]
print(f"Target index: {binary_search(0, a, value=33)}")
結(jié)果如下：
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Python裝飾器用法與知識(shí)點(diǎn)小結(jié)
這篇文章主要介紹了Python裝飾器用法與知識(shí)點(diǎn),總結(jié)分析了Python 裝飾器的基本概念、原理、用法與操作注意事項(xiàng),需要的朋友可以參考下2020-03-03
python實(shí)現(xiàn)將json多行數(shù)據(jù)傳入到mysql中使用
這篇文章主要介紹了python實(shí)現(xiàn)將json多行數(shù)據(jù)傳入到mysql中使用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12
Python使用tkinter模塊實(shí)現(xiàn)推箱子游戲
這篇文章主要介紹了Python使用tkinter模塊實(shí)現(xiàn)推箱子游戲,主要分享兩點(diǎn)，第一就是這個(gè)程序的實(shí)現(xiàn)過程，第二點(diǎn)就是我在編寫過程中的一些思考。本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友參看下吧2019-10-10
Python調(diào)用C++,通過Pybind11制作Python接口
今天小編就為大家分享一篇關(guān)于Python調(diào)用C++,通過Pybind11制作Python接口，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-10-10
python使用pandas處理excel文件轉(zhuǎn)為csv文件的方法示例
這篇文章主要介紹了python使用pandas處理excel文件轉(zhuǎn)為csv文件的方法示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
使用Fastapi打包exe后無限啟動(dòng)導(dǎo)致死機(jī)的解決辦法
將 fastapi 服務(wù)打包成 exe 后雙擊執(zhí)行,命令行中不斷創(chuàng)建服務(wù)導(dǎo)致cpu吃滿,最后死機(jī),所以本文給大家介紹了Fastapi打包exe后無限啟動(dòng)導(dǎo)致死機(jī)的解決辦法,需要的朋友可以參考下2024-03-03
不知道大家有沒有遇到過這樣的問題,就是在某個(gè)軟件或者某個(gè)網(wǎng)頁里面有一篇文章,你非常喜歡,但是不能復(fù)制.這個(gè)時(shí)候我們就會(huì)選擇截圖保存,但是當(dāng)我們想用到里面的文字時(shí),還是要一個(gè)字一個(gè)字打出來,那么能不能直接識(shí)別圖片中的文字呢？答案是肯定的,需要的朋友可以參考下2021-05-05
pytorch中 gpu與gpu、gpu與cpu 在load時(shí)相互轉(zhuǎn)化操作
這篇文章主要介紹了pytorch模型載入之gpu和cpu互轉(zhuǎn)操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-05-05
這篇文章主要為大家詳細(xì)介紹了基于python中theano庫的線性回歸，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-08-08
pandas之分組統(tǒng)計(jì)列聯(lián)表pd.crosstab()問題
這篇文章主要介紹了pandas之分組統(tǒng)計(jì)列聯(lián)表pd.crosstab()問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09