C語言實現二分查找：指標與遞歸版本完整代碼

遞歸二分查找函數

#include 

int binsearch(int low, int high, int *ptr, int value) {
    if (ptr == NULL || low > high) return -1;

    if (*(ptr + low) == value) { ptr += low; return low; }
    if (*(ptr + high) == value) { ptr += high; return high; }
    if (low == high) {
        if (*(ptr + low) == value) { ptr += low; return low; }
        return -1;
    }

    int mid = (low + high) / 2;
    if (*(ptr + mid) == value) { ptr += mid; return mid; }
    else if (*(ptr + mid) > value) return binsearch(low, mid - 1, ptr, value);
    else return binsearch(mid + 1, high, ptr, value);
}

int main() {
    int arr[10], *ptr = arr;
    for (int i = 0; i < 10; i++) scanf("%d", arr + i);
    printf("輸入查找值: "); int m; scanf("%d", &m);
    int idx = binsearch(0, 9, ptr, m);
    printf("索引: %d, 值: %d\n", idx, (idx >= 0) ? *(ptr + idx) : -1);
    return 0;
}

關鍵點解析

• 指標算術：ptr + i 直接定位第 i 元素，避免數組下標轉換。
• 遞歸終止條件：low > high、low == high、命中目標。
• 邊界縮減：mid - 1 / mid + 1 避免無限遞歸。
• 前提：數組已排序（升序）。

迭代版對比（更推薦）

int binsearch_iter(int *ptr, int n, int value) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防溢出
        if (ptr[mid] == value) return mid;
        else if (ptr[mid] < value) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

• 無函數調用開銷，無棧溢出風險。
• low + (high - low)/2 防止 low+high 溢出。

總結

遞歸版適合教學理解分治邏輯，生產環境優先用迭代版。注意數組必須有序，且指標參數需指向有效內存。