Python二分法搜索算法實(shí)例分析
本文實(shí)例分析了Python二分法搜索算法。分享給大家供大家參考。具體分析如下：
今天看書時(shí)，書上提到二分法雖然道理簡單，大家一聽就明白但是真正能一次性寫出別出錯的實(shí)現(xiàn)還是比較難的，即使給了你充足的時(shí)間，比如1小時(shí)。如果你不是特別認(rèn)真的話，可能還是會出一些這樣那樣的錯誤，所以就嘗試了自己去實(shí)現(xiàn)一下，看能否一次通過，結(jié)果自然不言而喻，雖然用的時(shí)間不長，但是我失敗了，呵呵。
個人覺得失敗的最主要原因是自己沒有認(rèn)真的先想好這個思路和可能出現(xiàn)的分支情況，而是直接憑主觀臆想就去寫代碼了，完全正中書上所說的行為，所以也如書上所說，出錯了。后經(jīng)調(diào)試應(yīng)該是得到了基本的正確算法，內(nèi)容如下：
#!/usr/bin/env python
#encoding: utf-8
def half_search(search_arr, search_str):
lb = 0
ub = len(search_arr) - 1
for i in range(ub/2 + 1):
if lb > ub:
return -1
mid = (ub + lb)/2
if search_arr[mid] == search_str:
return mid
elif search_arr[mid] > search_str:
ub = mid - 1
else:
lb = mid + 1
if __name__=='__main__':
arr = [10,20,30,40,50,60,70]
print half_search(arr, 1)
print half_search(arr, 11)
print half_search(arr, 22)
print half_search(arr, 33)
print half_search(arr, 40)
print half_search(arr, 55)
print half_search(arr, 66)
print half_search(arr, 70)
print half_search(arr, 8)
結(jié)果：
-1 -1 -1 -1 3 -1 -1 6 -1
正整數(shù)代表在數(shù)組中的下標(biāo)，3那就是第4個位置；-1代表不存在
總結(jié)：
實(shí)現(xiàn)簡單的算法之前，如果已經(jīng)有了一套最簡易的實(shí)現(xiàn)【比如直接打印100條相似的內(nèi)容】，不妨要想想是否還有更精巧的實(shí)現(xiàn)【可否用循環(huán)+參數(shù)化替代】；實(shí)現(xiàn)稍微復(fù)雜點(diǎn)的算法時(shí)，不妨先在紙上畫出各種可能的驗(yàn)證情況，避免實(shí)現(xiàn)是缺胳膊短腿的；還有一點(diǎn)就是算法什么的還是要多練，不然稍微復(fù)雜的過一陣可能就會忘記細(xì)節(jié)了。我想這就叫術(shù)業(yè)有專攻吧！
希望本文所述對大家的Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
python可視化數(shù)據(jù)分析pyecharts初步嘗試
這篇文章主要為大家介紹了python可視化數(shù)據(jù)分析pyecharts初步嘗試，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2022-04-04
這里簡單介紹了下Python中冒泡，選擇，插入排序的使用方法，推薦給需要的小伙伴們參考下。2015-02-02
這篇文章主要介紹了python讀取和輸出到txt，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
上手簡單,功能強(qiáng)大的Python爬蟲框架——feapder
這篇文章主要介紹了上手簡單,功能強(qiáng)大的Python爬蟲框架——feapder的使用教程，幫助大家更好的利用python進(jìn)行爬蟲，感興趣的朋友可以了解下2021-04-04
這篇文章主要介紹了python?中raise用法，Python?允許我們在程序中手動設(shè)置異常，就是使用raise?語句來實(shí)現(xiàn)，下面我們就來看看raise的具體用法，文章內(nèi)容介紹詳細(xì)，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2021-12-12
Python實(shí)現(xiàn)冒泡，插入，選擇排序簡單實(shí)例
這篇文章主要介紹了Python實(shí)現(xiàn)冒泡，插入，選擇排序簡單實(shí)例,很適合Python初學(xué)者學(xué)習(xí)參考之用,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了python中eval的用法及說明,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-09-09
python 通過手機(jī)號識別出對應(yīng)的微信性別(實(shí)例代碼)
這篇文章主要介紹了python 通過手機(jī)號識別出對應(yīng)的微信性別，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-12-12
python linecache讀取行更新的實(shí)現(xiàn)
本文主要介紹了python linecache讀取行更新的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
nginx+uwsgi+django環(huán)境搭建的方法步驟
這篇文章主要介紹了nginx+uwsgi+django環(huán)境搭建的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11