python中二分查找法的實(shí)現(xiàn)方法
如果想要在有序數(shù)據(jù)中進(jìn)行查找想要的數(shù)據(jù)，二分查找法就個(gè)好方法，它可以大大縮短了搜索時(shí)間，是一種常見的查找方法。二分查找很好寫，卻很難寫對(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 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))
基礎(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ū)域確定過程：
若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)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Python優(yōu)雅實(shí)現(xiàn)二分查找的示例詳解
- 使用Python實(shí)現(xiàn)二分法查找的示例
- Python實(shí)現(xiàn)二分法查找及優(yōu)化的示例詳解
- Python?二分查找之bisect庫(kù)的使用詳解
- Python算法練習(xí)之二分查找算法的實(shí)現(xiàn)
- 詳解Python查找算法的實(shí)現(xiàn)(線性,二分,分塊,插值)
- Python語(yǔ)言實(shí)現(xiàn)二分法查找
- python二分法查找函數(shù)底值
- python二分法查找實(shí)例代碼
- python實(shí)現(xiàn)二分查找算法
- python二分查找搜索算法的多種實(shí)現(xiàn)方法
相關(guān)文章
這篇文章主要為大家介紹了Python函數(shù)傳遞問題，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-11-11
這篇文章主要介紹了關(guān)于Numpy中數(shù)組維度的理解,多維Numpy數(shù)組也可以叫張量(tensor),當(dāng)前所有機(jī)器學(xué)習(xí)系統(tǒng)都是使用張量作為基本數(shù)據(jù)結(jié)構(gòu),張量是一個(gè)數(shù)據(jù)容器,它包含的數(shù)據(jù)幾乎是數(shù)值數(shù)據(jù),因此它也是數(shù)字的容器,需要的朋友可以參考下2023-09-09
使用python找出list列表中相同元素(指定元素)的所有索引
這篇文章主要給大家介紹了關(guān)于使用python找出list列表中相同元素(指定元素)的所有索引,在平時(shí)開發(fā)過程中經(jīng)常遇到需要在數(shù)據(jù)中獲取特定的元素索引的信息,需要的朋友可以參考下2023-08-08
在Python編程中,我們經(jīng)常需要處理各種類型的文件,其中包括二進(jìn)制文件,本文將詳細(xì)介紹如何使用Python讀寫二進(jìn)制文件,并提供一些實(shí)際應(yīng)用的示例,希望對(duì)大家有所幫助2024-01-01
今天小編就為大家分享一篇Opencv+Python 色彩通道拆分及合并的示例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2018-12-12
這篇文章主要介紹了python基于opencv批量生成驗(yàn)證碼的示例，幫助大家更好的理解和學(xué)習(xí)使用python，感興趣的朋友可以了解下2021-04-04
Python利用prettytable實(shí)現(xiàn)格式化輸出內(nèi)容
Python有一個(gè)第三方模塊叫?prettytable，專門用來(lái)將數(shù)據(jù)格式輸出。本文將通過示例為大家詳細(xì)講講prettytable的用法，感興趣的可以了解一下2022-07-07
Vs Code中8個(gè)好用的python 擴(kuò)展插件
這篇文章主要介紹了Vs Code中8個(gè)好用的python 擴(kuò)展插件，幫助大家更好的利用vs code進(jìn)行python開發(fā)，感興趣的朋友可以了解下2020-10-10
Python成功解決TypeError: ‘method’ object is
在Python編程中,有時(shí)候我們可能會(huì)遇到一個(gè)讓人摸不著頭腦的錯(cuò)誤信息：TypeError: 'method' object is not subscriptable,本文給大家介紹了Python如何成功解決TypeError: ‘method’ object is not subscriptable,需要的朋友可以參考下2024-06-06
python使用jpype導(dǎo)入多個(gè)Jar的異常問題及解決
這篇文章主要介紹了python使用jpype導(dǎo)入多個(gè)Jar的異常問題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12