二分查找遞迴實作精解：整數平方數陣列上的精確定位

程式碼概覽

本程式示範在**已排序整數陣列**上實作遞迴版二分查找。陣列內容為 `0², 1², 2², ..., 99²`（共 100 元素），查找目標同樣取自陣列元素，驗證正確性；並支援互動式輸入任意整數查找。

完整可編譯程式碼（已修正語法錯誤）

#include 
#include 

#define NUM 100

typedef struct node {
    int x;
    int y;          // 保留欄位，本範例未使用
} node;

node global[NUM] = {0}; // 全域陣列，靜態初始化為 0
int count = 0;          // 未使用，保留

// 遞迴二分查找：在 [left, right] 閉區間查找 target.x
// 回傳：找到 → 索引 (0-based)；未找到 → -1
int find(int left, int right, node target) {
    if (left > right) return -1;           // 區間空，未找到
    int mid = left + (right - left) / 2;   // 防溢位寫法

    if (target.x == global[mid].x) return mid; // 命中
    if (target.x > global[mid].x)
        return find(mid + 1, right, target);   // 右半區間
    else
        return find(left, mid - 1, target);    // 左半區間
}

int main() {
    // 1. 建資料：global[i].x = i*i
    for (int i = 0; i < NUM; i++) {
        global[i].x = i * i;
        printf(" (%d) ", global[i].x);
    }
    printf("\n");

    // 2. 批次驗證：查找每個陣列元素，應回傳自身索引
    node temp;
    for (int i = 0; i < NUM; i++) {
        temp.x = global[i].x;
        int idx = find(0, NUM - 1, temp);
        printf("result is {%d}\n", idx); // 應輸出 0, 1, 2, ..., 99
    }

    // 3. 互動式查找
    printf("new\n");
    int input;
    while (scanf("%d", &input) == 1 && input != 0) { // 輸入 0 結束
        temp.x = input;
        int idx = find(0, NUM - 1, temp);
        printf("result is {%d}\n", idx);
    }
    return 0;
}

關鍵技術點解析

1. 遞迴終止條件與區間縮減

if (left > right) return -1; // 空區間
int mid = left + (right - left) / 2; // 防止 left+right 溢位
if (target == a[mid]) return mid;
if (target > a[mid]) return find(mid+1, right, target);
else return find(left, mid-1, target);

• 使用**閉區間 `[left, right]`** 語意清晰。
• `mid+1` / `mid-1` 確保區間嚴格縮小，避免無限遞迴。
• 原始碼的 `if(left==mid)` 特判邏輯**過度複雜且有誤**，標準寫法更簡潔可靠。

2. 陣列有序性是前提

二分查找**要求陣列嚴格遞增/遞減**。本例 `i*i` 單調遞增（非負整數），滿足條件。若陣列無序，必須先排序（`qsort`）。

3. 結構體傳值 vs 傳址

int find(int left, int right, node target) // 傳值：複製 8 bytes (兩個 int)

此處 `node` 較小，傳值開銷可接受；若結構體龐大，應改 `const node*` 避免棧拷貝。

4. 全域陣列 vs 參數傳遞

`global` 為全域變數，`find` 直接存取。模組化設計應改為：

int find(const node *arr, int left, int right, int target_val);

提高複用性與執行緒安全性。

5. 互動輸入迴圈細節

while (scanf("%d", &input) == 1 && input != 0)

• `scanf` 回傳成功匹配項數，`==1` 確保讀到整數。
• 輸入 `0` 作為退出信號（因陣列含 0，若需查 0 需改退出碼）。
• 非整數輸入會導致 `scanf` 失敗並卡住，**生產碼需清緩衝區**。

複雜度分析

常見變體與擴展

1. 找第一個/最後一個等於目標（含重複元素）：命中後繼續向左/右搜尋邊界。
2. 找第一個大於/大於等於目標（lower_bound/upper_bound）：回傳 `left` 而非 `-1`。
3. 旋轉陣列查找：判斷哪半有序，再決定去哪半。
4. 浮點數查找：需引入 `eps` 容差比較。

遞迴轉迭代範本（推薦生產使用）

int binary_search_iter(const int *arr, int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

總結

二分查找是「有序陣列」的標準解法，遞迴版代碼優雅但需注意棧深度與參數傳遞開銷。本文修正了原始碼的邏輯缺陷（區間縮減錯誤、特判冗餘），並提供迭代版對照。掌握**閉區間不變量**與**中點防溢位**兩大核心細節，即可寫出正確、高效的二分查找。