快捷導(dǎo)航

Pythonic版二分查找實(shí)現(xiàn)過程原理解析

更新時(shí)間：2020年08月11日 14:27:58 作者：天外歸云

這篇文章主要介紹了Pythonic版二分查找實(shí)現(xiàn)過程原理解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

前提：升序數(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)方法
這篇文章主要介紹了python單例模式的多種實(shí)現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2019-07-07
Python深入淺出分析元類
在Python里一切都是對(duì)象（object），基本數(shù)據(jù)類型，如數(shù)字，字符串，函數(shù)都是對(duì)象。對(duì)象可以由類（class）進(jìn)行創(chuàng)建。那么既然一切都是對(duì)象，那么類是對(duì)象嗎？是的，類也是對(duì)象，那么又是誰創(chuàng)造了類呢？答案也很簡單，也是類，一個(gè)能創(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í)例講解)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
2017-07-07
Django框架多表查詢實(shí)例分析
這篇文章主要介紹了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ì)，對(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
python下載安裝requests庫的簡單步驟
這篇文章主要給大家介紹了關(guān)于python下載安裝requests庫的簡單步驟,使用Python的requests庫下載文件是一種常見的操作,文中通過圖文介紹的非常詳細(xì),需要的朋友可以參考下
2023-11-11
對(duì)Python 窗體(tkinter)文本編輯器(Text)詳解
今天小編就為大家分享一篇對(duì)Python 窗體(tkinter)文本編輯器(Text)詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2018-10-10
Python?seaborn數(shù)據(jù)可視化繪圖(直方圖,密度圖,散點(diǎn)圖)
這篇文章主要介紹了Python?seaborn數(shù)據(jù)可視化繪圖(直方圖,密度圖,散點(diǎn)圖)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的朋友可以參考一下
2022-07-07