Python實(shí)現(xiàn)二分法算法實(shí)例

更新時(shí)間：2015年02月02日 09:39:46 投稿：junjie

這篇文章主要介紹了Python實(shí)現(xiàn)二分法算法實(shí)例,本文先是介紹了算法規(guī)則,然后給出了實(shí)現(xiàn)例子,需要的朋友可以參考下

1.算法：（設(shè)查找的數(shù)組期間為array[low, high]）

（1）確定該期間的中間位置K
（2）將查找的值T與array[k]比較。若相等，查找成功返回此位置；否則確定新的查找區(qū)域，繼續(xù)二分查找。區(qū)域確定如下：

a.array[k]>T 由數(shù)組的有序性可知array[k,k+1,……,high]>T;故新的區(qū)間為array[low,……，K-1]
b.array[k]<T 類似上面查找區(qū)間為array[k+1,……，high]。每一次查找與中間值比較，可以確定是否查找成功，不成功當(dāng)前查找區(qū)間縮小一半。遞歸找，即可。

復(fù)制代碼代碼如下:

#!/usr/bin/python
# -*- coding: utf-8 -*-

def BinarySearch(array,t):
low = 0
height = len(array)-1
while low <= height:
mid = (low+height)/2
if array[mid] < t:
low = mid + 1

elif array[mid] > t:
height = mid - 1

else:
return array[mid]

return -1

if __name__ == "__main__":
print BinarySearch([1,2,3,34,56,57,78,87],57)

結(jié)果：57

3.時(shí)間復(fù)雜度:O(log2n);

注意：二分查找的前提必須待查找的序列有序。

您可能感興趣的文章:

相關(guān)文章

基于Python實(shí)現(xiàn)報(bào)表自動(dòng)化并發(fā)送到郵箱
作為數(shù)據(jù)分析師，我們需要經(jīng)常制作統(tǒng)計(jì)分析圖表。但是報(bào)表太多的時(shí)候往往需要花費(fèi)我們大部分時(shí)間去制作報(bào)表。本文將利用Python實(shí)現(xiàn)報(bào)表自動(dòng)化并發(fā)送到郵箱，需要的可以參考一下
2022-07-07
python中小數(shù)點(diǎn)后取2位(四舍五入)及取2位(四舍五不入)的方法
這篇文章主要給大家介紹了python中小數(shù)點(diǎn)后取2位(四舍五入)及取2位(四舍五不入)的方法,在Python中取兩位小數(shù)的方法其實(shí)非常簡(jiǎn)單,需要的朋友可以參考下
2023-08-08
Python用Pillow(PIL)進(jìn)行簡(jiǎn)單的圖像操作方法
下面小編就為大家?guī)硪黄狿ython用Pillow(PIL)進(jìn)行簡(jiǎn)單的圖像操作方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
2017-07-07
python編程調(diào)用設(shè)備串口發(fā)送數(shù)據(jù)方式
這篇文章主要介紹了python編程調(diào)用設(shè)備串口發(fā)送數(shù)據(jù)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2023-09-09
Python基于Floyd算法求解最短路徑距離問題實(shí)例詳解
這篇文章主要介紹了Python基于Floyd算法求解最短路徑距離問題,結(jié)合完整實(shí)例形式詳細(xì)分析了Python使用Floyd算法求解最短路徑距離問題的相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下
2018-05-05
計(jì)算python腳本執(zhí)行時(shí)間的多種方法
在編寫Python腳本時(shí),了解腳本的執(zhí)行時(shí)間通常是很有用的,特別是在優(yōu)化代碼或評(píng)估性能時(shí),Python提供了多種方法來測(cè)量腳本的執(zhí)行時(shí)間,從內(nèi)置模塊到第三方庫(kù),可以選擇適合你需求的方式,本文將介紹計(jì)算 Python 腳本執(zhí)行時(shí)間的多種方法,需要的朋友可以參考下
2023-11-11
python 循環(huán)遍歷字典元素的簡(jiǎn)單方法
下面小編就為大家?guī)硪黄猵ython循環(huán)遍歷字典元素的簡(jiǎn)單方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
2016-09-09
pandas 根據(jù)列的值選取所有行的示例
今天小編就為大家分享一篇pandas 根據(jù)列的值選取所有行的示例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2018-11-11
詳解python關(guān)于多級(jí)包之間的引用問題
本文主要介紹了python關(guān)于多級(jí)包之間的引用問題，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-08-08
numpy中幾種隨機(jī)數(shù)生成函數(shù)的用法
numpy是Python中常用的科學(xué)計(jì)算庫(kù),其中也包含了一些隨機(jī)數(shù)生成函數(shù),本文主要介紹了numpy中幾種隨機(jī)數(shù)生成函數(shù)的用法,具有一定的參考價(jià)值,感興趣的可以了解一下
2023-11-11