C語言二分查找常見錯誤分析與標準實現模板

原始代碼錯誤定位

用戶提供的代碼存在四個關鍵錯誤，涉及數組名拼寫、條件判斷邏輯、分支結構、邊界更新：

// 原代碼片段
int arr[5];
for(i=0; i<5; i++) scanf("%d\n", &a[i]);  // 錯誤1: 數組名寫成 a
// ...
if(j==a[mid]);  // 錯誤2: 分號導致 if 空執行
{ break; }
else if (j<a[mid]) high=mid-1;
}  // 錯誤3: 多餘右大括號導致 else 匹配錯誤
else low=mid+1;  // 錯誤4: 缺少對應的 if

標準二分查找實現模板

前提條件

• 數組必須有序 (升序或降序，邏輯對應調整)
• 數組下標從 0 開始，長度為 n，有效區間 [0, n-1]

模板代碼 (查找目標值 target)

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

int binary_search(const int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防止 low+high 溢出
        if (arr[mid] == target)
            return mid;                    // 找到，返回下標
        else if (arr[mid] < target)
            low = mid + 1;                 // 目標在右半部
        else
            high = mid - 1;                // 目標在左半部
    }
    return -1;                             // 未找到
}

int main(void) {
    int n = 5, target;
    int arr[5];
    printf("請輸入5個有序整數(空格分隔): ");
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);  // 修正: 用 arr, 格式串無 \n
    printf("請輸入查找值: ");
    scanf("%d", &target);
    int idx = binary_search(arr, n, target);
    if (idx != -1)
        printf("找到，下標: %d\n", idx);
    else
        printf("未找到\n");
    return 0;
}

關鍵細節深度解析

1. 中間值計算防溢出

mid = low + (high - low) / 2 等價於 (low + high) / 2，但避免了 low + high 超過 INT_MAX 導致溢出錯誤，是工業級寫法。

2. 循環條件 low <= high

區間為閉區間 [low, high]，當 low == high 時仍有 1 個元素需檢查，故用 <=。若用 low < high 則漏檢單元素情況。

3. 邊界更新策略

• low = mid + 1：排除 mid 及左側，新區間 [mid+1, high]
• high = mid - 1：排除 mid 及右側，新區間 [low, mid-1]

確保區間嚴格縮小，避免死循環。

4. 返回值語義

返回下標 (0-based) 而非元素值，便於後續操作 (如插入、刪除、統計)。未找到返回 -1 (或其他約定哨兵值)。

常見變體擴展

查找第一個 ≥ target 的位置 (lower_bound)

int lower_bound(const int arr[], int n, int target) {
    int low = 0, high = n;  // 高邊界開區間 [low, high)
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid;
    }
    return low;  // 可能等於 n (所有元素均 < target)
}

查找最後一個 ≤ target 的位置

int upper_bound(const int arr[], int n, int target) {
    int low = 0, high = n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= target)
            low = mid + 1;
        else
            high = mid;
    }
    return low - 1;  // 可能為 -1 (所有元素均 > target)
}

調試建議與測試用例

總結

二分查找核心在於「有序性利用」與「區間縮減」。掌握標準模板、防溢出寫法、邊界更新邏輯及常見變體，是算法面試與工程實踐的基本功。原代碼錯誤多為語法疏忽 (分號、大括號、變量名)，培養代碼審查習慣、善用編譯器警告 (-Wall -Wextra) 可有效避免。