二分搜尋演算法：遞迴版本完整實作與邊界條件分析

二分搜尋是有序陣列查找的標準演算法，O(log n) 時間複雜度。本文提供標準遞迴實作，詳細分析邊界條件、中點計算溢位、終止條件等易錯點，並給出迭代版對比。

標準遞迴實作

#include <stdio.h>
#include <stdlib.h>

int binary_search_recursive(const int *arr, int left, int right, int target) {
    if (left > right) return -1;  // 區間為空，未找到
    
    int mid = left + (right - left) / 2;  // 防溢位寫法
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)
        return binary_search_recursive(arr, mid + 1, right, target);
    else
        return binary_search_recursive(arr, left, mid - 1, target);
}

// 包裝函式
int binary_search(const int *arr, int n, int target) {
    return binary_search_recursive(arr, 0, n - 1, target);
}

關鍵細節深度解析

1. 中點計算防溢位

mid = (left + right) / 2 在 left+right > INT_MAX 時溢位（負數導致死迴圈）。標準寫法：

mid = left + (right - left) / 2;      // 整數除法向零截斷
// 或
mid = (left + right) >> 1;            // 位移等效，無溢位
// 或 (C11/C++11)
mid = (unsigned)(left + right) / 2;   // 無號運算不溢位

2. 區間定義：左閉右閉 [left, right]

• 初始呼叫：left=0, right=n-1
• 遞迴縮小：[mid+1, right] 或 [left, mid-1]
• 終止條件：left > right 表示區間空

統一用左閉右閉，邏輯最直觀，不易出現 Off-by-one 錯誤。

3. 終止條件順序

必須先檢查 left > right 再計算 mid，否則空區間存取 arr[mid] 導致 UB。

4. 遞迴深度

最大深度 ⌊log₂ n⌋ + 1。n=10⁹ 時深度約 30，堆疊安全。但嵌入式系統堆疊受限時改用迭代版。

迭代版（生產環境首選）

int binary_search_iterative(const int *arr, int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

優勢：無函式呼叫開銷、無堆疊溢位風險、編譯器易優化為條件移動指令。

變體：下界/上界查找

測試驗證

int main() {
    int arr[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    for (int i = 0; i < n; i++) {
        int idx = binary_search(arr, n, arr[i]);
        printf("找 %3d -> 索引 %d %s\n", arr[i], idx, idx==i?"✓":"✗");
    }
    
    // 不存在的值
    printf("找 50 -> %d (預期 -1)\n", binary_search(arr, n, 50));
    printf("找 0  -> %d (預期 -1)\n", binary_search(arr, n, 0));
    printf("找 101-> %d (預期 -1)\n", binary_search(arr, n, 101));
    return 0;
}

常見錯誤清單

1. mid = (left+right)/2 溢位
2. 遞迴呼叫未 return，導致結果丟失
3. 區間縮小錯誤：mid 而非 mid±1，造成無限遞迴
4. 終止條件寫成 left == right，漏檢單元素區間
5. 陣列未排序就呼叫二分搜尋

總結

二分搜尋核心在於「有序性」與「區間不變式」。掌握左閉右閉區間、防溢位中點、正確縮小邊界三要素，遞迴與迭代版均能寫出正確、高效的代碼。面試白板編程建議直接寫迭代版，並主動說明防溢位與變體擴展。