您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言問答

C 語言折半查找 (二分查找) 算法原理與代碼實現完整指南

編輯：C 語言問答

C 語言折半查找 (二分查找) 算法原理與代碼實現完整指南

折半查找 要求數據已排序，每次將搜索範圍減半，時間複雜度 O(log n)，遠優於線性查找 O(n)。

算法核心邏輯

設定左右邊界 `low=0, high=n-1`
循環條件 `low <= high`
計算中間位置 `mid = low + (high - low) / 2` (防溢出)
比較 `arr[mid]` 與目標值 `target`：

相等 → 返回 `mid`
目標較小 → `high = mid - 1` (搜左半)
目標較大 → `low = mid + 1` (搜右半)

循環結束未找到 → 返回 -1

標準迭代實現

int binary_search(const int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防止 (low+high) 溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;  // 未找到
}

遞歸實現

int binary_search_rec(const int arr[], int low, int high, int target) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binary_search_rec(arr, mid + 1, high, target);
    return binary_search_rec(arr, low, mid - 1, target);
}

實戰演示

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};  // 已排序
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 23;

    int idx = binary_search(arr, n, target);
    if (idx != -1)
        printf("找到 %d 於索引 %d\n", target, idx);  // 索引 5
    else
        printf("未找到\n");

    return 0;
}

關鍵細節與變體

場景	修改點
查找第一個 ≥ target (下界)	`arr[mid] >= target` 時 `high = mid - 1`，返回 `low`
查找最後一個 ≤ target (上界)	`arr[mid] <= target` 時 `low = mid + 1`，返回 `high`
查找第一次出現 (有重複)	相等時 `high = mid - 1`，記錄候選答案
查找最後一次出現	相等時 `low = mid + 1`，記錄候選答案
浮點數數組	比較用 epsilon 範圍判斷相等
旋轉有序數組	判斷哪半有序，再決定去哪半

複雜度分析

時間：O(log₂ n) —— 每輪範圍減半，最多 ⌊log₂ n⌋ + 1 輪
空間：迭代 O(1)、遞歸 O(log n) (棧幀)
前提：必須有序，否則結果不可預期

標準庫函數

#include <stdlib.h>
// bsearch 通用二分查找，需提供比較函數
int cmp_int(const void *a, const void *b) {
    return *(const int*)a - *(const int*)b;
}
int *found = bsearch(&target, arr, n, sizeof(int), cmp_int);