二分查找法怎么在python項目中實現？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
1、二分查找
在一個有序并且無重復的列表中，對該列表的元素進行查找。
2、特點
（1）必須針對于有序列表
（2）該列表必須無重復
（3）按下標索引查找
3、使用方法
非遞歸實現：
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))遞歸實現：
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]比較，若相等，查找成功返回此位置；否則確定新的查找區域，繼續二分查找。
3）區域確定過程：
若array[k]>t，由于數組有序，所以array[k,k+1,……,high]>t；故新的區間為array[low, ..., K-1]；
反之，若array[k]<t對應查找區間為array[k+1, ..., high]
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
