Pythonic版二分查找實(shí)現(xiàn)過程原理解析
前提：升序數(shù)組，待查元素在數(shù)組中。
二分查找：就是一個遞歸函數(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)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了python單例模式的多種實(shí)現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-07-07
在Python里一切都是對象（object），基本數(shù)據(jù)類型，如數(shù)字，字符串，函數(shù)都是對象。對象可以由類（class）進(jìn)行創(chuàng)建。那么既然一切都是對象，那么類是對象嗎？是的，類也是對象，那么又是誰創(chuàng)造了類呢？答案也很簡單，也是類，一個能創(chuàng)作類的類，稱之為(type)元類2022-07-07
Python 實(shí)現(xiàn)給圖片加文字或logo水印
本文主要為大家介紹了給圖片添加文字或者logo圖片水印的python工具，從而打造你的專屬圖片。代碼簡潔易懂，感興趣的小伙伴可以了解一下2021-11-11
python數(shù)據(jù)結(jié)構(gòu)鏈表之單向鏈表(實(shí)例講解)
下面小編就為大家?guī)硪黄猵ython數(shù)據(jù)結(jié)構(gòu)鏈表之單向鏈表(實(shí)例講解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07
這篇文章主要介紹了Django框架多表查詢,結(jié)合實(shí)例形式分析了Django框架實(shí)現(xiàn)多表查詢的外鍵、關(guān)聯(lián)、前向查詢、反向查詢等相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下2018-07-07
自定義實(shí)現(xiàn) PyQt5 下拉復(fù)選框 ComboCheckBox的完整代碼
這篇文章主要介紹了自定義實(shí)現(xiàn) PyQt5 下拉復(fù)選框 ComboCheckBox的完整代碼，本文通過實(shí)例代碼講解的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03
解決python繪圖使用subplots出現(xiàn)標(biāo)題重疊的問題
這篇文章主要介紹了python繪圖使用subplots出現(xiàn)標(biāo)題重疊的問題及解決方法，本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-04-04
這篇文章主要給大家介紹了關(guān)于python下載安裝requests庫的簡單步驟,使用Python的requests庫下載文件是一種常見的操作,文中通過圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-11-11
對Python 窗體(tkinter)文本編輯器(Text)詳解
今天小編就為大家分享一篇對Python 窗體(tkinter)文本編輯器(Text)詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10
Python?seaborn數(shù)據(jù)可視化繪圖(直方圖,密度圖,散點(diǎn)圖)
這篇文章主要介紹了Python?seaborn數(shù)據(jù)可視化繪圖(直方圖,密度圖,散點(diǎn)圖)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的朋友可以參考一下2022-07-07