python有序查找算法 二分法實例解析
這篇文章主要介紹了python有序查找算法 二分法實例解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
二分法是一種快速查找的方法,時間復雜度低,邏輯簡單易懂,總的來說就是不斷的除以2除以2...
但是需要注意:
待查找的序列區(qū)間單調(diào)有序
例如需要查找有序數(shù)組arr里面的某個關鍵字key的位置,那么首先確認arr的中位數(shù)或者中點center,下面分為三種情況:
假如arr[center]>key,說明key在arr中心左邊范圍;
假如arr[center]<key,說明key在arr中心右邊范圍;
假如arr[center]=key,說明key在arr中心。
范圍每次縮小一半,寫個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: # 建立一個死循環(huán),直到找到key while True: # 得到中位數(shù) # 這里一定要加int,防止列表是偶數(shù)的時候出現(xià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) + "個位置") 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("請輸入你要查找的數(shù)字:") if key == " ": print("謝謝使用!") break else: BinarySearch(arr, int(key))
運行結(jié)果:
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
Python使用plt庫實現(xiàn)繪制動態(tài)曲線圖并導出為GIF或MP4
這篇文章主要為大家詳細介紹了Python如何使用plt庫實現(xiàn)繪制動態(tài)曲線圖并導出為GIF或MP4,文中的示例代碼講解詳細,需要的可以了解一下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解決方法,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-07-07使用Python裝飾器在Django框架下去除冗余代碼的教程
這篇文章主要介紹了使用Python裝飾器在Django框架下去除冗余代碼的教程,主要是處理JSON代碼的一些冗余,需要的朋友可以參考下2015-04-04Python實現(xiàn)生成隨機數(shù)據(jù)插入mysql數(shù)據(jù)庫的方法
這篇文章主要介紹了Python實現(xiàn)生成隨機數(shù)據(jù)插入mysql數(shù)據(jù)庫的方法,涉及Python隨機字符串生成及數(shù)據(jù)庫連接、插入等相關操作技巧,需要的朋友可以參考下2017-12-12python實現(xiàn)動態(tài)創(chuàng)建類的方法分析
這篇文章主要介紹了python實現(xiàn)動態(tài)創(chuàng)建類的方法,結(jié)合實例形式分析了Python動態(tài)創(chuàng)建類的原理、實現(xiàn)方法及相關操作技巧,需要的朋友可以參考下2019-06-06