C語言遞歸二分查找：指針算術與邊界條件深度解析

前言：為什麼用指針實現二分查找？

二分查找是算法入門必修課。用指針算術替代下標索引，不僅能加深對 C 語言內存模型的理解，更能在嵌入式開發、底層庫編寫中寫出更緊湊、高效的代碼。本文基於一個遞歸版實現，重點剖析指針偏移邏輯、遞歸終止條件、以及常見的「無限遞歸」陷阱。

一、 代碼架構與核心邏輯

#include <stdio.h>

// 函數聲明：low/high 為下標邊界，ptr 指向數組首地址
int binsearch(int low, int high, int *ptr, int value);

int main() {
    int arr[10];
    int *ptr = arr; // 指向首元素
    // ... 輸入數據 (假設已升序排列) ...
    int m; scanf("%d", &m);
    int pos = binsearch(0, 9, ptr, m);
    if (pos != -1) printf("找到於下標 %d, 值 %d\n", pos, *(ptr + pos));
    else printf("未找到\n");
    return 0;
}

// 遞歸二分查找
int binsearch(int low, int high, int *ptr, int value) {
    // 1. 遞歸基線條件：區間無效
    if (ptr == NULL || low > high) return -1;

    // 2. 邊界快速判斷 (優化: 減少遞歸深度)
    if (*(ptr + low) == value)  return low;
    if (*(ptr + high) == value) return high;

    // 3. 區間縮減至單元素
    if (low == high) return -1; // 上已判斷過 low/high 不等於 value

    // 4. 計算中點 (防溢出寫法: low + (high - low) / 2)
    int mid = low + (high - low) / 2;
    int mid_val = *(ptr + mid);

    // 5. 核心遞歸分支
    if (mid_val == value) {
        return mid;
    } else if (mid_val > value) {
        return binsearch(low, mid - 1, ptr, value); // 左半區間
    } else {
        return binsearch(mid + 1, high, ptr, value); // 右半區間
    }
}

二、 關鍵技術點深度剖析

1. 指針算術 vs 下標訪問

• *(ptr + mid) 等價於 ptr[mid]，編譯器生成相同機器碼。
• 優勢：解耦「邏輯下標」與「物理地址」。若需在子數組中查找，可直接傳遞 ptr + offset 並調整 low/high 為相對下標，無需複製數組。

2. 遞歸終止條件的「三重保險」

1. low > high：標準區間為空判斷。
2. low == high：單元素區間，若前序邊界檢查未命中，直接返回 -1。
3. ptr == NULL：防禦性編程，防止空指針解引用。

常見錯誤：僅判斷 low > high 而漏掉 low == high 的顯式處理，導致 mid = low 陷入 binsearch(low, mid-1, ...) 或 binsearch(mid+1, high, ...) 形成 low > high 才終止，雖正確但多一次遞歸。

3. 避免無限遞歸的關鍵：區間必須嚴格縮小

// 錯誤示範：導致無限遞歸
if (mid_val > value) return binsearch(low, mid, ptr, value); // mid 未排除
// 正確寫法：
if (mid_val > value) return binsearch(low, mid - 1, ptr, value); // 排除 mid

原代碼中 mid-1 和 mid+1 確保了區間長度單調遞減，遞歸深度上限為 $O(\log n)$。

4. 中點計算的溢出隱患

(low + high) / 2 在 low + high > INT_MAX 時溢出（雖本例 n=10 無礙）。標準寫法：low + (high - low) / 2 或 (low + high) >> 1 (無符號數安全)。

三、 遞歸 vs 迭代：性能與棧開銷

建議：教學/邏輯複雜場景用遞歸；高性能/嵌入式/數據量大用迭代。

四、 進階擴展：泛型二分查找 (模擬 C++ 模板/qsort 風格)

// 使用 void* + 比較函數指針 實現泛型
int binsearch_generic(void *base, size_t nmemb, size_t size,
                      const void *key, int (*cmp)(const void *, const void *)) {
    char *arr = (char *)base;
    int low = 0, high = nmemb - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int res = cmp(arr + mid * size, key);
        if (res == 0) return mid;
        else if (res > 0) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}
// 調用: binsearch_generic(arr, 10, sizeof(int), &key, cmp_int);

總結

指針版遞歸二分查找，核心在於精確的區間縮減邏輯 (mid±1) 與 完備的基線條件 (low>=high)。掌握指針算術與遞歸邊界，是寫出正確、高效 C 代碼的關鍵一步。建議動手實現迭代版、泛型版，並對比生成的彙編代碼，深化理解。

1. 上一篇文章： C語言字符串拼接實戰：指鉤操作與標準庫函數對比
2. 下一篇文章： C語言編譯全流程深度解析：從源碼到可執行文件

關於C語言

带头节点单链表就地逆序算法详解

问题定义 给定带头节点的单链表 head → 1 → 2 →

C 語言線性表順序儲存結構完整實作：動態擴容、增刪查改

一、抽象資料型別 (ADT) 定義 // Sqlist.h

C 語言指針作為函數參數應用：交換變量與冒泡排序實戰

核心概念 C 語言參數傳遞為**值傳遞**。若需在函數內修改

單鏈表反轉三大算法圖解：從暴力破解到原地指針操作的極致優雅

問題：如何反轉單鏈表？ 給定單鏈表 head → 1 → 2