C 語言折半查找（二分查找）標準實現：遞歸與迭代

迭代版（推薦生產）

int binarySearch(int *a, int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int m = l + (r - l) / 2; // 防溢出
        if (x < a[m]) r = m - 1;
        else if (x > a[m]) l = m + 1;
        else return m; // 找到返回下標
    }
    return -1; // 未找到
}

遞歸版（教學）

int binarySearchRec(int *a, int l, int r, int x) {
    if (l > r) return -1;
    int m = l + (r - l) / 2;
    if (x < a[m]) return binarySearchRec(a, l, m-1, x);
    if (x > a[m]) return binarySearchRec(a, m+1, r, x);
    return m;
}

測試主程序

int main() {
    int a[] = {1,2,3,4,5,6,7,8};
    int idx = binarySearch(a, 8, 8);
    printf("%s\n", idx==-1 ? "not exist" : "found");
    return 0;
}

關鍵細節

• 前提：數組**已升序排列**；
• m = l + (r-l)/2 防止 l+r 溢出；
• 返回下標而非值，便於後續操作；
• 迭代版無棧溢出風險，生產首選。