Python 二分搜尋演算法實作與邊界條件分析

二分搜尋邏輯簡單但邊界條件易錯，本文提供經測試的正確實作與常見陷阱分析。

正確實作

def half_search(arr, target):
    lb, ub = 0, len(arr) - 1
    for _ in range(ub // 2 + 1):
        if lb > ub:
            return -1
        mid = (lb + ub) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            ub = mid - 1
        else:
            lb = mid + 1
    return -1

測試案例

arr = [10, 20, 30, 40, 50, 60, 70]
tests = [1, 11, 22, 33, 40, 55, 66, 70, 8]
for t in tests:
    print(half_search(arr, t))
# 輸出：-1 -1 -1 -1 3 -1 -1 6 -1

關鍵點

• 迴圈上限 ub//2 + 1 確保足夠迭代次數
• lb > ub 作為未找到終止條件
• 索引更新 mid ± 1 避免無限迴圈
• 回傳索引 (0-based) 或 -1 表示不存在

心得

1. 實作前先在紙上推演邊界情況
2. 簡單演算法也要考慮參數化與迴圈替代重複代碼
3. 定期練習避免生疏