python有序查找算法 二分法實(shí)例解析
這篇文章主要介紹了python有序查找算法 二分法實(shí)例解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
二分法是一種快速查找的方法，時(shí)間復(fù)雜度低，邏輯簡(jiǎn)單易懂，總的來說就是不斷的除以2除以2...
但是需要注意：
待查找的序列區(qū)間單調(diào)有序
例如需要查找有序數(shù)組arr里面的某個(gè)關(guān)鍵字key的位置，那么首先確認(rèn)arr的中位數(shù)或者中點(diǎn)center，下面分為三種情況：
假如arr[center]>key，說明key在arr中心左邊范圍；
假如arr[center]<key，說明key在arr中心右邊范圍；
假如arr[center]=key，說明key在arr中心。
范圍每次縮小一半，寫個(gè)while的死循環(huán)知道找到為止。
二分法查找非?？烨曳浅３Ｓ?，但是唯一要求是要求數(shù)組是有序的
二分法的代碼如下：
#!/usr/bin/python3.4
# -*- 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("沒有該數(shù)字!")
if __name__ == "__main__":
arr = [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93]
while True:
key = input("請(qǐng)輸入你要查找的數(shù)字：")
if key == " ":
print("謝謝使用！")
break
else:
BinarySearch(arr, int(key))
運(yùn)行結(jié)果：
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
django+xadmin+djcelery實(shí)現(xiàn)后臺(tái)管理定時(shí)任務(wù)
這篇文章主要介紹了django+xadmin+djcelery實(shí)現(xiàn)后臺(tái)管理定時(shí)任務(wù)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-08-08
利用selenium爬蟲抓取數(shù)據(jù)的基礎(chǔ)教程
這篇文章主要給大家介紹了關(guān)于如何利用selenium爬蟲抓取數(shù)據(jù)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用selenium具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06
教你從零開始實(shí)現(xiàn)貪吃蛇Python小游戲
這篇文章主要教你從零開始實(shí)現(xiàn)貪吃蛇Python小游戲,沒有使用pygame庫(kù),附帶源碼和注釋,非常有意思,需要的朋友可以參考下2023-03-03
今天小編就為大家分享一篇python得到電腦的開機(jī)時(shí)間方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-10-10
一文學(xué)會(huì)使用OpenCV構(gòu)建文檔掃描儀
本文將使用 OpenCV,創(chuàng)建一個(gè)簡(jiǎn)單的文檔掃描儀,就像常用的攝像頭掃描儀應(yīng)用程序一樣,這篇文章主要給大家介紹了關(guān)于使用OpenCV構(gòu)建文檔掃描儀的相關(guān)資料,需要的朋友可以參考下2022-11-11
Python?cv.Canny()方法參數(shù)與使用方法
這篇文章主要介紹了Python?cv.Canny()方法參數(shù)與使用方法，OpenCV提供了cv.Canny()方法，該方法將輸入的原始圖像轉(zhuǎn)換為邊緣圖像，更多相關(guān)內(nèi)容需要的朋友可以參考一下2022-07-07
使用python爬取連續(xù)降水?dāng)?shù)據(jù)信息實(shí)例
這篇文章主要為大家介紹了使用python提取連續(xù)降水?dāng)?shù)據(jù)信息實(shí)現(xiàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01
Python編寫可視化界面的詳細(xì)教程(Python+PyCharm+PyQt)
最近開始學(xué)習(xí)Python,但只限于看理論,編幾行代碼,覺得沒有意思,就想能不能用Python編寫可視化的界面,遂查找了相關(guān)資料,發(fā)現(xiàn)了PyQt,所以本文介紹了Python+PyCharm+PyQt編寫可視化界面的詳細(xì)教程,需要的朋友可以參考下2024-07-07
python在Windows8下獲取本機(jī)ip地址的方法
這篇文章主要介紹了python在Windows8下獲取本機(jī)ip地址的方法,涉及Python中socket包相關(guān)函數(shù)的使用技巧,需要的朋友可以參考下2015-03-03
Python函數(shù)any()和all()的用法及區(qū)別介紹
any函數(shù)：any(x)，只要x中有一個(gè)不為空，0，false就返回True，否則返回False。all(x)函數(shù)必須x中的所有元素均不為空，0，false才會(huì)返回True，否則返回False。接下來通過本文給大家介紹Python函數(shù)any()和all()的用法及區(qū)別介紹，需要的朋友參考下吧2018-09-09