Python有序查找算法之二分法實(shí)例分析
本文實(shí)例講述了Python有序查找算法之二分法。分享給大家供大家參考，具體如下：
二分法是一種快速查找的方法，時(shí)間復(fù)雜度低，邏輯簡(jiǎn)單易懂，總的來(lái)說(shuō)就是不斷的除以2除以2...
例如需要查找有序數(shù)組arr里面的某個(gè)關(guān)鍵字key的位置，那么首先確認(rèn)arr的中位數(shù)或者中點(diǎn)center，下面分為三種情況：
① 假如arr[center]>key，說(shuō)明key在arr中心左邊范圍；
② 假如arr[center]<key，說(shuō)明key在arr中心右邊范圍；
③ 假如arr[center]=key，說(shuō)明key在arr中心。
范圍每次縮小一半，寫(xiě)個(gè)while的死循環(huán)知道找到為止。
二分法查找非?？烨曳浅３Ｓ?，但是唯一要求是要求數(shù)組是有序的
前面一篇冒泡排序可以去看看：
http://www.dbjr.com.cn/article/130288.htm
二分法的代碼如下：
# -*- coding: utf-8 -*-
def BinarySearch(arr, key):
# 記錄數(shù)組的最高位和最低位
min = 0
max = len(arr) - 1
if key in arr:
# 建立一個(gè)死循環(huán)，直到找到key
while True:
# 得到中位數(shù)
# 這里一定要加int，防止列表是偶數(shù)的時(shí)候出現(xiàn)浮點(diǎn)數(shù)據(jù)
center = int((min + max) / 2)
# key在數(shù)組左邊
if arr[center] > key:
max = center - 1
# key在數(shù)組右邊
elif arr[center] < key:
min = center + 1
# key在數(shù)組中間
elif arr[center] == key:
print(str(key) + "在數(shù)組里面的第" + str(center) + "個(gè)位置")
return arr[center]
else:
print("沒(méi)有該數(shù)字!")
if __name__ == "__main__":
print("腳本之家測(cè)試結(jié)果：")
arr = [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93]
while True:
key = raw_input("請(qǐng)輸入你要查找的數(shù)字：")
if key == " ":
print("謝謝使用！")
break
else:
BinarySearch(arr, int(key))
運(yùn)行結(jié)果：
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
文章詳細(xì)介紹了Numpy中vstack()和hstack()兩種數(shù)組拼接方法,vstack()是垂直堆疊數(shù)組,需保證除第一軸（行）外,數(shù)組形狀相同,hstack()是按順序堆疊數(shù)組,需保證除第二軸（列）外,數(shù)組形狀相同,兩者都可通過(guò)堆疊給定數(shù)組最后形成至少二維的數(shù)組2024-10-10
python實(shí)現(xiàn)自動(dòng)登錄后臺(tái)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)自動(dòng)登錄后臺(tái)管理系統(tǒng)，并進(jìn)行后續(xù)操作，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-10-10
Python+Selenium實(shí)現(xiàn)短視頻自動(dòng)上傳與發(fā)布的實(shí)踐
本文主要介紹了Python+Selenium實(shí)現(xiàn)短視頻自動(dòng)上傳與發(fā)布的實(shí)踐，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
這篇文章主要介紹了Django+Gunicorn+Nginx部署之路，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
Python IndexError報(bào)錯(cuò)分析及解決方法
在Python編程中,IndexError是一種常見(jiàn)的異常類(lèi)型,它通常發(fā)生在嘗試訪問(wèn)序列（如列表、元組或字符串）中不存在的索引時(shí),本文將深入分析IndexError的成因、表現(xiàn)形式,并提供相應(yīng)的解決辦法,同時(shí)附帶詳細(xì)的代碼示例,需要的朋友可以參考下2024-07-07
python使用ctypes調(diào)用擴(kuò)展模塊的實(shí)例方法
在本篇文章里小編給大家整理的是一篇關(guān)于python使用ctypes調(diào)用擴(kuò)展模塊的實(shí)例方法內(nèi)容，需要的朋友們可以學(xué)習(xí)參考下。2020-01-01
Python3多進(jìn)程 multiprocessing 模塊實(shí)例詳解
這篇文章主要介紹了Python3多進(jìn)程 multiprocessing 模塊,結(jié)合實(shí)例形式詳細(xì)分析了Python3多進(jìn)程 multiprocessing 模塊的概念、原理、相關(guān)方法使用技巧與注意事項(xiàng),需要的朋友可以參考下2018-06-06
這篇文章主要為大家詳細(xì)介紹了python微信好友數(shù)據(jù)分析，實(shí)現(xiàn)對(duì)微信好友的獲取，并對(duì)省份、性別等數(shù)據(jù)分析，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-11-11
這篇文章主要為大家詳細(xì)介紹了用python實(shí)現(xiàn)打磚塊小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
今天給大家?guī)?lái)的是關(guān)于Python的相關(guān)知識(shí),文章圍繞著lambda函數(shù)用法展開(kāi),文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06