二分查找算法正确实现：迭代版与递归版完整代码

經典難題

Bentley 在《Writing Correct Programs》指出：90% 程式設計師無法在 2 小時內寫出完全正確的二分搜尋。關鍵難點在於邊界條件處理。

迭代版（推薦生產環境使用）

int search(int array[], int n, int v) {
    int left = 0, right = n - 1, middle;

    while (left <= right) {           // 區間 [left, right] 非空
        middle = (left + right) / 2;  // 向下取整
        if (array[middle] > v)
            right = middle - 1;       // 目標在左半區間 [left, middle-1]
        else if (array[middle] < v)
            left = middle + 1;        // 目標在右半區間 [middle+1, right]
        else
            return middle;            // 找到
    }
    return -1;                        // 不存在
}

關鍵點解析

• 循環條件 left <= right：對應閉區間 [left, right]，單元素區間 left==right 仍需檢查。
• 縮小區間：right = middle - 1 / left = middle + 1，確保 middle 不會被再次檢查，避免死循環。
• 中點計算：(left + right) / 2 可能溢位，工程上建議 left + (right - left) / 2 或 (left + right) >> 1。

遞歸版

int search_recurse(int array[], int low, int high, int v) {
    if (low > high) return -1;              // 區間為空
    int middle = (low + high) / 2;
    if (array[middle] > v)
        return search_recurse(array, low, middle - 1, v);
    else if (array[middle] < v)
        return search_recurse(array, middle + 1, high, v);
    else
        return middle;
}

簡化邏輯

原文遞歸版對 low == high 單獨處理屬冗餘。標準遞歸寫法統一以 low > high 為終止條件，涵蓋所有情況。

測試主程式

int main() {
    int array[] = {0,1,2,3,4,5,6,7,13,19};
    int n = sizeof(array) / sizeof(array[0]);

    int m = search(array, n, 13);
    printf("Iterative: m = %d\n", m);  // 輸出 8

    m = search_recurse(array, 0, n - 1, 13);
    printf("Recursive: m = %d\n", m);  // 輸出 8
    return 0;
}

常見錯誤避坑指南

擴展：lower_bound / upper_bound 模式

尋找第一個 ≥ value / > value 的位置，區間寫法為 [left, right)，循環條件 left < right，回傳 left。此模式更統一、不易出錯，C++ STL 採用此慣例。