簡(jiǎn)介二分查找算法與相關(guān)的Python實(shí)現(xiàn)示例
更新時(shí)間：2015年08月26日 12:12:26 作者：buaa_shang
這篇文章主要介紹了二分查找算法與相關(guān)的Python實(shí)現(xiàn)示例,Binary Search同時(shí)也是算法學(xué)習(xí)當(dāng)中最基礎(chǔ)的知識(shí),需要的朋友可以參考下
二分查找Binary Search的思想：
以有序表表示靜態(tài)查找表時(shí)，查找函數(shù)可以用二分查找來(lái)實(shí)現(xiàn)。
二分查找（Binary Search）的查找過(guò)程是：先確定待查記錄所在的區(qū)間，然后逐步縮小區(qū)間直到找到或找不到該記錄為止。
1二分查找的時(shí)間復(fù)雜度是O(log(n))，最壞情況下的時(shí)間復(fù)雜度是O(n)。
假設(shè) low 指向區(qū)間下界，high 指向區(qū)間上界，mid 指向區(qū)間的中間位置，則 mid = （low + high) / 2;
具體過(guò)程：
1.先將關(guān)鍵字與 mid 指向的元素比較，如果相等則返回mid。
2.關(guān)鍵字小于 mid 指向的元素關(guān)鍵字，則在 [ low, mid-1 ]區(qū)間中繼續(xù)進(jìn)行二分查找。
3.關(guān)鍵字大于mid 指向的元素關(guān)鍵字，則在[ mid +1 , high] 區(qū)間中繼續(xù)進(jìn)行二分查找。
用Python實(shí)現(xiàn)二分查找示例：
>>> def find(self, num):
l = len(self)
first = 0
end = l - 1
mid = 0
if l == 0:
self.insert(0,num)
return False
while first < end:
mid = (first + end)/2
if num > self[mid]:
first = mid + 1
elif num < self[mid]:
end = mid - 1
else:
break
if first == end:
if self[first] > num:
self.insert(first, num)
return False
elif self[first] < num:
self.insert(first + 1, num)
return False
else:
return True
elif first > end:
self.insert(first, num)
return False
else:
return True
>>> list_d = ['a','b','c','d','e','f','d','t']
>>> value_d = 't'
>>> aa=find(list_d,value_d)
>>> aa
True
>>> value_d='ha'
>>> aa=find(list_d,value_d)
>>> aa
False
相關(guān)文章
今天小編就為大家分享一篇在Python中定義一個(gè)常量的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-11-11
這篇文章主要介紹了Python如何執(zhí)行系統(tǒng)命令，幫助大家更好的利用python操作系統(tǒng)，感興趣的朋友可以了解下2020-09-09
HTTPX是Python3的功能齊全的HTTP客戶端，它提供同步和異步API，本文主要介紹了python-httpx的具體使用，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
圖文詳解Python中如何簡(jiǎn)單地解決Microsoft?Visual?C++?14.0報(bào)錯(cuò)
有的時(shí)候安裝python依賴包的時(shí)候,報(bào)錯(cuò)信息"Microsoft?visual?c++?14.0?is?required"的解決辦法,下面這篇文章主要給大家介紹了關(guān)于Python中如何簡(jiǎn)單地解決Microsoft?Visual?C++?14.0報(bào)錯(cuò)的相關(guān)資料,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了如何使用Python監(jiān)控屏幕變化并截圖,文中通過(guò)代碼示例給大家講解的非常詳細(xì),并對(duì)大家的學(xué)習(xí)工作有一定的幫助,需要的朋友可以參考下2024-04-04
python函數(shù)存儲(chǔ)在模塊的優(yōu)點(diǎn)及用法總結(jié)
在本篇文章里小編給大家整理了一篇關(guān)于python函數(shù)存儲(chǔ)在模塊的優(yōu)點(diǎn)及用法相關(guān)內(nèi)容，有興趣的朋友們可以跟著學(xué)習(xí)下。2021-10-10
Python3.5集合及其常見(jiàn)運(yùn)算實(shí)例詳解
這篇文章主要介紹了Python3.5集合及其常見(jiàn)運(yùn)算,結(jié)合實(shí)例形式分析了Python3.5集合的定義、功能、交集、并集、差集等常見(jiàn)操作技巧與相關(guān)注意事項(xiàng),需要的朋友可以參考下2019-05-05
Python中的 is 和 == 以及字符串駐留機(jī)制詳解
這篇文章主要介紹了Python中的 is 和 == 以及字符串駐留機(jī)制詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-06-06
利用Python的pandas數(shù)據(jù)處理包將寬表變成窄表
這篇文章主要介紹了利用Python的pandas數(shù)據(jù)處理包將寬表變成窄表，文章通過(guò)圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09
大家都知道使用csv文件可以較容易地存儲(chǔ)多行且列相同的數(shù)據(jù),便于數(shù)據(jù)的讀取與解析,也常用于自動(dòng)化測(cè)試過(guò)程中的數(shù)據(jù)參數(shù)化,下面這篇文章主要給大家介紹了關(guān)于如何利用Python處理CSV文件的相關(guān)資料,需要的朋友可以參考下2022-06-06