python中二分查找法的實現(xiàn)方法
如果想要在有序數(shù)據(jù)中進行查找想要的數(shù)據(jù)，二分查找法就個好方法，它可以大大縮短了搜索時間，是一種常見的查找方法。二分查找很好寫，卻很難寫對，下面，小編就簡單向大家介紹一下二分查找，并演示器使用代碼。
1、二分查找
在一個有序并且無重復的列表中，對該列表的元素進行查找。
2、特點
（1）必須針對于有序列表
（2）該列表必須無重復
（3）按下標索引查找
3、使用方法
非遞歸實現(xiàn)：
def binary_search(alist, item):
"""二分查找 非遞歸方式"""
n = len(alist)
start = 0
end = n - 1
while start <= end:
mid = (start + end) // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
end = mid - 1
else:
start = mid + 1
return False
if __name__ == '__main__':
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
# print(binary_search(li, 55))
# print(binary_search(li, 100))
遞歸實現(xiàn)：
def binary_search_2(alist, item):
"""二分查找 遞歸方式"""
n = len(alist)
if 0 == n:
return False
mid = n // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search_2(alist[:mid], item)
else:
return binary_search_2(alist[mid + 1:], item)
if __name__ == '__main__':
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
# print(binary_search(li, 55))
# print(binary_search(li, 100))
基礎知識點擴展：
介紹
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。
前提
必須待查找的序列有序
時間復雜度
O(log2n)
原理
1）確定該期間的中間位置K
2）將查找的值t與array[k]比較，若相等，查找成功返回此位置；否則確定新的查找區(qū)域，繼續(xù)二分查找。
3）區(qū)域確定過程：
若array[k]>t，由于數(shù)組有序，所以array[k,k+1,……,high]>t；故新的區(qū)間為array[low, ..., K-1]；
反之，若array[k]<t對應查找區(qū)間為array[k+1, ..., high]
到此這篇關于python中二分查找法的實現(xiàn)方法的文章就介紹到這了,更多相關python中二分查找法如何實現(xiàn)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Python高并發(fā)和多線程有什么關系,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
這篇文章主要為大家詳細介紹了python實現(xiàn)圖片轉字符畫，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-02-02
今天小編就為大家分享一篇利用Pytorch實現(xiàn)簡單的線性回歸算法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01
用Python從0開始實現(xiàn)一個中文拼音輸入法的思路詳解
中文輸入法是一個歷史悠久的問題，但也實在是個繁瑣的活，不知道這是不是網上很少有人分享中文拼音輸入法的原因，接下來通過本文給大家分享使用Python從0開始實現(xiàn)一個中文拼音輸入法,需要的朋友可以參考下2019-07-07
Pycharm?debug程序,跳轉至指定循環(huán)條件/循環(huán)次數(shù)問題
這篇文章主要介紹了Pycharm?debug程序,跳轉至指定循環(huán)條件/循環(huán)次數(shù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
全角與半角轉換在處理漢語語料中會經常出現(xiàn),這里分別說明漢字、數(shù)字、字母的unicode編碼范圍,下面這篇文章主要給大家介紹了關于Python全角與半角之間相互轉換的相關資料,需要的朋友可以參考下2022-03-03
在Python編程中，filter()函數(shù)是一個有用的工具，用于篩選可迭代對象（如列表、元組等）中滿足特定條件的元素，本文就來詳細的介紹一下Python?filter函數(shù)的具體使用，感興趣的可以了解一下2024-01-01
這篇文章主要介紹了教你怎么用Python實現(xiàn)多路徑迷宮,文中有非常詳細的代碼示例,對正在學習python的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-04-04
Python Matplotlib庫實現(xiàn)畫局部圖
這篇文章主要為大家詳細介紹了Python Matplotlib庫實現(xiàn)畫局部圖，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
本文不談復雜的理論，就經驗教大家字符處理八字真言：確定編碼，同類交互。教大家快速戰(zhàn)勝Python字符編碼。2016-08-08