您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關(guān)python中怎么實(shí)現(xiàn)二分查找法的內(nèi)容。小編覺得挺實(shí)用的,因此分享給大家做個參考。一起跟隨小編過來看看吧。
1、二分查找:在一個有序并且無重復(fù)的列表中,對該列表的元素進(jìn)行查找。
2、特點(diǎn)
(1)必須針對于有序列表
(2)該列表必須無重復(fù)
(3)按下標(biāo)索引查找
3、使用方法
非遞歸實(shí)現(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))
遞歸實(shí)現(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))
雖然二分查找的效率高,但是要將表按關(guān)鍵字排序。而排序本身是一種很費(fèi)時的運(yùn)算。即使采用高效率的排序方法也要花費(fèi)O(nlgn)的時間。而且二分查找只適用順序存儲結(jié)構(gòu),鏈表上無法實(shí)現(xiàn)二分查找。
感謝各位的閱讀!關(guān)于python中怎么實(shí)現(xiàn)二分查找法就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,讓大家可以學(xué)到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。