您好,登錄后才能下訂單哦!
這篇文章主要介紹python如何實現有序查找算法,文中介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們一定要看完!
二分法是一種快速查找的方法,時間復雜度低,邏輯簡單易懂,總的來說就是不斷的除以2除以2...
但是需要注意:
待查找的序列區(qū)間單調有序
例如需要查找有序數組arr里面的某個關鍵字key的位置,那么首先確認arr的中位數或者中點center,下面分為三種情況:
假如arr[center]>key,說明key在arr中心左邊范圍;
假如arr[center]<key,說明key在arr中心右邊范圍;
假如arr[center]=key,說明key在arr中心。
范圍每次縮小一半,寫個while的死循環(huán)知道找到為止。
二分法查找非常快且非常常用,但是唯一要求是要求數組是有序的
二分法的代碼如下:
#!/usr/bin/python3.4 # -*- coding: utf-8 -*- def BinarySearch(arr, key): # 記錄數組的最高位和最低位 min = 0 max = len(arr) - 1 if key in arr: # 建立一個死循環(huán),直到找到key while True: # 得到中位數 # 這里一定要加int,防止列表是偶數的時候出現浮點數據 center = int((min + max) / 2) # key在數組左邊 if arr[center] > key: max = center - 1 # key在數組右邊 elif arr[center] < key: min = center + 1 # key在數組中間 elif arr[center] == key: print(str(key) + "在數組里面的第" + str(center) + "個位置") return arr[center] else: print("沒有該數字!") if __name__ == "__main__": arr = [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93] while True: key = input("請輸入你要查找的數字:") if key == " ": print("謝謝使用!") break else: BinarySearch(arr, int(key))
運行結果:
以上是“python如何實現有序查找算法”這篇文章的所有內容,感謝各位的閱讀!希望分享的內容對大家有幫助,更多相關知識,歡迎關注億速云行業(yè)資訊頻道!
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。