C 語言實作二分搜尋（遞迴與迴圈版）

前置條件

陣列已排序（升序）。二分搜尋每次將搜尋範圍減半，時間複雜度 O(log N)。

遞迴版

int bin_search_rec(const int *arr, int low, int high, int key) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2; // 防溢位
    if (arr[mid] == key) return mid;
    if (key > arr[mid]) return bin_search_rec(arr, mid + 1, high, key);
    return bin_search_rec(arr, low, mid - 1, key);
}

迴圈版（推薦生產環境）

int bin_search_iter(const int *arr, int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) return mid;
        if (key > arr[mid]) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

完整可執行程式

#include <stdio.h>

int bin_search_rec(const int *a, int low, int high, int k);
int bin_search_iter(const int *a, int n, int k);

int main() {
    int A[10] = {2,3,5,7,8,10,12,15,19,21};
    printf("Array: ");
    for (int i=0;i<10;i++) printf("%d ", A[i]);
    printf("\nInput key to search: ");
    int key; scanf("%d", &key);
    int pos = bin_search_iter(A, 10, key);
    if (pos != -1) printf("Found at index %d (0-based)\n", pos);
    else printf("Not found\n");
    return 0;
}

int bin_search_rec(const int *a, int low, int high, int k) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == k) return mid;
    if (k > a[mid]) return bin_search_rec(a, mid+1, high, k);
    return bin_search_rec(a, low, mid-1, k);
}

int bin_search_iter(const int *a, int n, int k) {
    int low=0, high=n-1;
    while (low<=high) {
        int mid = low + (high-low)/2;
        if (a[mid]==k) return mid;
        if (k>a[mid]) low=mid+1;
        else high=mid-1;
    }
    return -1;
}

關鍵細節

• mid 計算：用 low + (high-low)/2 避免 low+high 溢位（雖本題 N=10 無虞）。
• 回傳值：找到回傳索引（0-based），找不到回傳 -1。
• 邊界：low <= high 為迴圈條件，遞迴基底 low > high。

擴展：標準庫 bsearch

#include <stdlib.h>
int cmp_int(const void *a, const void *b) { return *(int*)a - *(int*)b; }
int *found = bsearch(&key, A, 10, sizeof(int), cmp_int);