在排序演算法之後，我們終於要介紹一個非常經典且實用的搜尋演算法 —— 二元搜尋 (Binary Search)。如果說排序演算法是「把資料整理好」，那麼搜尋演算法就是「如何在整理好的資料中快速找到想要的元素」。二元搜尋憑藉著「折半」的概念，將搜尋的時間複雜度大幅降低。

演算法概念

二元搜尋的基本思想是:

• 前提：資料必須是 有序的陣列 (升冪或降冪都可以，但必須一致)。
• 方法：每次將搜尋範圍對半切割，並檢查中間元素。
• 若中間元素剛好等於目標值 → 成功找到。
• 若目標值小於中間元素 → 在左半邊繼續搜尋。
• 若目標值大於中間元素 → 在右半邊繼續搜尋。

透過「每次將搜尋範圍減半」，演算法的效率大幅提升。

演算法步驟

1. 設定左邊界 left = 0，右邊界 right = n - 1。
2. 當 left <= right 時，計算中間索引 mid = (left + right) // 2。
3. 如果 arr[mid] == target，回傳 mid。
4. 如果 arr[mid] > target，將右邊界移到 mid - 1。
5. 如果 arr[mid] < target，將左邊界移到 mid + 1。
6. 若最終沒有找到，回傳 -1（表示不存在）。

程式碼範例

Iterative 版本

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 測試
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))   # 輸出: 3
print(binary_search(arr, 2))   # 輸出: -1

Recursive 版本

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 測試
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search_recursive(arr, 7, 0, len(arr)-1))   # 輸出: 3
print(binary_search_recursive(arr, 2, 0, len(arr)-1))   # 輸出: -1

複雜度分析

• 時間複雜度: 每次搜尋範圍縮小一半，最多重複 log2(n) 次。
  • 最佳情況: $O(1)$ (剛好中間值就是目標)。
  • 最壞情況: $O(\log n)$。
  • 平均情況: $O(\log n)$。
• 空間複雜度
  • Iterative 版本: $O(1)$。
  • Recursive 版本: 因遞迴棧的存在，$O(\log n)$。

優缺點

結語

二元搜尋是一個簡單卻威力強大的演算法，它清楚展現了「減少搜尋範圍」能帶來的效率提升。雖然它只適用於有序資料，但在演算法設計中，「化問題為二分判斷」是一個常見且強大的思維模式。理解二元搜尋後，往後你在刷演算法題時會發現，許多問題都能用「Binary Search on Answer」這個技巧來解。