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í)現(xiàn)給圖片加文字或logo水印
本文主要為大家介紹了給圖片添加文字或者logo圖片水印的python工具,從而打造你的專屬圖片。代碼簡潔易懂,感興趣的小伙伴可以了解一下2021-11-11python數(shù)據(jù)結(jié)構(gòu)鏈表之單向鏈表(實(shí)例講解)
下面小編就為大家?guī)硪黄猵ython數(shù)據(jù)結(jié)構(gòu)鏈表之單向鏈表(實(shí)例講解)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-07-07自定義實(shí)現(xiàn) PyQt5 下拉復(fù)選框 ComboCheckBox的完整代碼
這篇文章主要介紹了自定義實(shí)現(xiàn) PyQt5 下拉復(fù)選框 ComboCheckBox的完整代碼,本文通過實(shí)例代碼講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03解決python繪圖使用subplots出現(xiàn)標(biāo)題重疊的問題
這篇文章主要介紹了python繪圖使用subplots出現(xiàn)標(biāo)題重疊的問題及解決方法,本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-04-04對(duì)Python 窗體(tkinter)文本編輯器(Text)詳解
今天小編就為大家分享一篇對(duì)Python 窗體(tkinter)文本編輯器(Text)詳解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-10-10Python?seaborn數(shù)據(jù)可視化繪圖(直方圖,密度圖,散點(diǎn)圖)
這篇文章主要介紹了Python?seaborn數(shù)據(jù)可視化繪圖(直方圖,密度圖,散點(diǎn)圖),文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的朋友可以參考一下2022-07-07