已發布·持續改進
Algorithm
搜尋演算法用於在資料中找出值或位置，涵蓋線性搜尋、二分搜尋、lower_bound 與 upper_bound、對答案二分搜尋以及雜湊查詢。
搜尋是在一組資料中找到目標值，或找出某個條件第一次成立的位置。線性搜尋逐一比較元素，適用於任何資料；二分搜尋每一步都把已排序的區間縮小一半，即使有一百萬個元素也只需要大約 20 次比較。如果只需要精確比對鍵值，雜湊表平均能在常數時間內回答。
幾乎每個程式都需要查詢資料，因此搜尋是最基礎的演算法之一。資料庫索引、自動完成、日誌分析和路由表都仰賴它。二分搜尋也不只用於陣列：只要一個是/否條件在某個範圍內只改變一次，就能直接對答案進行二分搜尋。如此一來，程式面試中的許多最佳化問題都能寫成簡短又可靠的程式碼。
建議先親手寫出線性搜尋與閉區間的二分搜尋，再練習半開區間的 lower_bound 與 upper_bound 寫法，直到邊界處理變得自然。用小陣列手動追蹤執行過程，以隨機輸入把自己的程式碼與 Python 的 bisect 模組比對驗證，最後透過最佳化問題練習對答案二分搜尋與三分搜尋。
逐一比較元素，耗時 O(n)。不需要排序，在元素不多時常常是最快的選擇。
每一步把已排序的區間縮小一半，在 O(log n) 時間內找到目標值。以迴圈實作只需要 O(1) 的額外記憶體。
回傳第一個大於等於或嚴格大於目標值的位置。兩者的差就是重複元素的個數，Python 的 bisect 模組同時提供這兩個函式。
參數搜尋把「可行的最小值是多少」轉換成是/否判斷，再在所有可能答案的範圍內進行二分搜尋。
lower_bound 使用半開區間 [lo, hi)，回傳第一個值大於等於 x 的索引。若中間值小於 x，就捨棄左半部，否則捨棄右半部。contains 利用這個索引判斷值是否存在，最後一行確認結果與標準函式庫的 bisect.bisect_left 相同。
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.py共六章，帶你從安裝一步步認識 搜尋 的核心概念。
在這裡提問、分享經驗，交流關於 搜尋 的看法。
還沒有討論。來發起第一則吧。
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。