C 語言二分搜尋法實作與常見錯誤分析

編輯：關於C語言

C 語言二分搜尋法實作與常見錯誤分析

正確實作

#include <stdio.h>

int binary_search(const int arr[], int len, int key) {
    int left = 0, right = len - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢位
        if (key == arr[mid]) return mid;
        else if (key > arr[mid]) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 未找到
}

int main() {
    int arr[] = {1, 3, 4, 5, 6, 7, 9, 13, 15, 36};
    int len = sizeof(arr) / sizeof(arr[0]);
    int key;
    printf("請輸入要查找的數: ");
    scanf("%d", &key);
    int pos = binary_search(arr, len, key);
    if (pos != -1)
        printf("找到 %d，位置索引 %d (第 %d 個)\n", key, pos, pos+1);
    else
        printf("不存在\n");
    return 0;
}

常見錯誤與修正

錯誤代碼	問題	修正
`if (left = right)`	使用賦值 `=` 而非比較 `==`	改為 `if (left > right)` 或直接檢查返回值
`mid = (left + right) / 2`	大陣列時 `left+right` 可能溢位	用 `left + (right-left)/2`
陣列未排序	二分搜尋前提是有序陣列	確保資料已排序
傳入長度錯誤	用 `sizeof(arr)` 而非元素個數	`sizeof(arr)/sizeof(arr[0])`

遞迴版本

int binary_search_rec(const int arr[], int left, int right, int key) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (key == arr[mid]) return mid;
    if (key > arr[mid]) return binary_search_rec(arr, mid+1, right, key);
    return binary_search_rec(arr, left, mid-1, key);
}

迭代版本因無函數呼叫開銷，效能略優於遞迴，建議實務上使用迭代。