python二分法查找算法實現(xiàn)方法【遞歸與非遞歸】
本文實例講述了python二分法查找算法實現(xiàn)方法。分享給大家供大家參考，具體如下：
二分法查找
二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
二分法查找實現(xiàn)
（非遞歸實現(xiàn)）
def binary_search(alist, item):
first = 0
last = len(alist)-1
while first<=last:
midpoint = (first + last)/2
if alist[midpoint] == item:
return True
elif item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
（遞歸實現(xiàn)）
def binary_search(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return True
else:
if item<alist[midpoint]:
return binary_search(alist[:midpoint],item)
else:
return binary_search(alist[midpoint+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
運行結(jié)果：
False
True
時間復(fù)雜度
- 最優(yōu)時間復(fù)雜度：O(1)
- 最壞時間復(fù)雜度：O(logn)
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python列表(list)操作技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
使用Windows批處理和WMI設(shè)置Python的環(huán)境變量方法
今天小編就為大家分享一篇使用Windows批處理和WMI設(shè)置Python的環(huán)境變量方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-08-08
Python 利用scrapy爬蟲通過短短50行代碼下載整站短視頻
近日，有朋友向我求助一件小事兒，他在一個短視頻app上看到一個好玩兒的段子，想下載下來，可死活找不到下載的方法。經(jīng)過我的一番研究才找到解決方法，下面小編給大家分享Python 利用scrapy爬蟲通過短短50行代碼下載整站短視頻的方法，感興趣的朋友一起看看吧2018-10-10
Django使用Celery實現(xiàn)異步發(fā)送郵件
這篇文章主要為大家詳細(xì)介紹了Django如何使用Celery實現(xiàn)異步發(fā)送郵件的功能，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-04-04
本文帶你了解CSV文件的基礎(chǔ)知識，那么當(dāng)需要處理導(dǎo)入數(shù)據(jù)時，大多數(shù)?CSV?讀取、處理和寫入任務(wù)都可以通過基本的?Python?csv?庫輕松處理。如果大量數(shù)據(jù)要讀取和處理，該pandas庫還提供快速簡便的?CSV?處理功能2022-04-04
利用Python實現(xiàn)自動生成小學(xué)生計算題
過年期間發(fā)現(xiàn)小外甥已經(jīng)上小學(xué)了，我姐說老師今天給他們布置了寒假作業(yè)：每天堅持做乘法和加減法混合運算。這我必須幫幫忙，用Python寫了一段自動生成小學(xué)生計算題的代碼，希望外甥不要太感謝我2023-02-02
這篇文章主要介紹了Python圖算法,結(jié)合實例形式詳細(xì)分析了Python數(shù)據(jù)結(jié)構(gòu)與算法中的圖算法實現(xiàn)技巧,需要的朋友可以參考下2016-08-08
這篇文章主要介紹了Python將QQ聊天記錄生成詞云的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
今天小編就為大家分享一篇快速解決vue.js 模板和jinja 模板沖突的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07
python獲取http請求響應(yīng)頭headers中的數(shù)據(jù)的示例
這篇文章主要介紹了python獲取http請求響應(yīng)頭headers中的數(shù)據(jù)，本文通過示例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-02-02
TensorFlow人工智能學(xué)習(xí)創(chuàng)建數(shù)據(jù)實現(xiàn)示例詳解
這篇文章主要為大家介紹了TensorFlow人工智能學(xué)習(xí)創(chuàng)建數(shù)據(jù)實現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2021-11-11