如果想要在有序數(shù)據(jù)中進(jìn)行查找想要的數(shù)據(jù)，二分查找法就個(gè)好方法，它可以大大縮短了搜索時(shí)間，是一種常見(jiàn)的查找方法。二分查找很好寫(xiě)，卻很難寫(xiě)對(duì)，下面，小編就簡(jiǎn)單向大家介紹一下二分查找，并演示器使用代碼。

1、二分查找

在一個(gè)有序并且無(wú)重復(fù)的列表中，對(duì)該列表的元素進(jìn)行查找。

2、特點(diǎn)

（1）必須針對(duì)于有序列表

（2）該列表必須無(wú)重復(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 Falseif __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))

基礎(chǔ)知識(shí)點(diǎn)擴(kuò)展：

介紹

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

前提

必須待查找的序列有序

時(shí)間復(fù)雜度

O(log2n)

原理

1）確定該期間的中間位置K

2）將查找的值t與array[k]比較，若相等，查找成功返回此位置；否則確定新的查找區(qū)域，繼續(xù)二分查找。

3）區(qū)域確定過(guò)程：

若array[k]>t，由于數(shù)組有序，所以array[k,k+1,……,high]>t；故新的區(qū)間為array[low, ..., K-1]；

反之，若array[k]<t對(duì)應(yīng)查找區(qū)間為array[k+1, ..., high]

到此這篇關(guān)于python中二分查找法的實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)python中二分查找法如何實(shí)現(xiàn)內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！