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)知道找到為止。
二分法查找非??烨曳浅3S茫俏ㄒ灰笫且髷?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)文章
windows下python模擬鼠標(biāo)點(diǎn)擊和鍵盤輸示例
這篇文章主要介紹了windows下python模擬鼠標(biāo)點(diǎn)擊和鍵盤輸示例,需要的朋友可以參考下2014-02-02Python使用plt庫實(shí)現(xiàn)繪制動(dòng)態(tài)曲線圖并導(dǎo)出為GIF或MP4
這篇文章主要為大家詳細(xì)介紹了Python如何使用plt庫實(shí)現(xiàn)繪制動(dòng)態(tài)曲線圖并導(dǎo)出為GIF或MP4,文中的示例代碼講解詳細(xì),需要的可以了解一下2024-03-03error?conda:ProxyError:Conda?cannot?proceed?due?to?an?
這篇文章主要為大家介紹了error conda:ProxyError:Conda cannot proceed due to an error in your proxy configuration解決方法,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-07-07使用Python裝飾器在Django框架下去除冗余代碼的教程
這篇文章主要介紹了使用Python裝飾器在Django框架下去除冗余代碼的教程,主要是處理JSON代碼的一些冗余,需要的朋友可以參考下2015-04-04Python如何使用Scapy實(shí)現(xiàn)端口探測(cè)
Scapy 是一款使用純Python編寫的跨平臺(tái)網(wǎng)絡(luò)數(shù)據(jù)包操控工具,它能夠處理和嗅探各種網(wǎng)絡(luò)數(shù)據(jù)包,本文主要介紹了Python如何使用使用Scapy實(shí)現(xiàn)端口探測(cè),有需要的可以參考下2023-10-10Python實(shí)現(xiàn)生成隨機(jī)數(shù)據(jù)插入mysql數(shù)據(jù)庫的方法
這篇文章主要介紹了Python實(shí)現(xiàn)生成隨機(jī)數(shù)據(jù)插入mysql數(shù)據(jù)庫的方法,涉及Python隨機(jī)字符串生成及數(shù)據(jù)庫連接、插入等相關(guān)操作技巧,需要的朋友可以參考下2017-12-12python實(shí)現(xiàn)動(dòng)態(tài)創(chuàng)建類的方法分析
這篇文章主要介紹了python實(shí)現(xiàn)動(dòng)態(tài)創(chuàng)建類的方法,結(jié)合實(shí)例形式分析了Python動(dòng)態(tài)創(chuàng)建類的原理、實(shí)現(xiàn)方法及相關(guān)操作技巧,需要的朋友可以參考下2019-06-06