C語言二分查找（折半查找）算法原理與完整代碼實現

什麼是二分查找？

二分查找，又稱折半查找，是一種高效的查找算法。其核心優勢在於查找速度極快，時間複雜度僅為 O(log n)；但前提條件是待查找的數據序列必須是有序的（升序或降序均可）。

算法核心思想

算法採用「分治」策略：

1. 取序列中間位置的元素與目標值比較
2. 若相等，查找成功，返回下標
3. 若目標值小於中間元素，則在左半部分繼續查找
4. 若目標值大於中間元素，則在右半部分繼續查找
5. 重複上述過程，直到找到目標或查找區間為空

完整 C 語言代碼實現

#include <stdio.h>

int binarySearch(int a[], int n, int key) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid;  // 找到，返回下標
    }
    return -1;  // 未找到
}

int main() {
    int i, val, ret;
    int a[8] = {-32, 12, 16, 24, 36, 45, 59, 98};
    
    printf("原始有序序列：\n");
    for (i = 0; i < 8; i++)
        printf("%d\t", a[i]);
    
    printf("\n請輸入所要查找的元素：");
    scanf("%d", &val);
    
    ret = binarySearch(a, 8, val);
    if (ret == -1)
        printf("查找失敗\n");
    else
        printf("查找成功，元素位於下標 %d\n", ret);
    
    return 0;
}

運行結果示例

原始有序序列：
-32 12 16 24 36 45 59 98
請輸入所要查找的元素：12
查找成功，元素位於下標 1

查找過程圖解

以查找 12 為例：

• 初始區間 [0,7]，mid=3，a[3]=24 > 12，縮小到左半區間 [0,2]
• 區間 [0,2]，mid=1，a[1]=12 = 目標值，查找成功，返回下標 1

整個過程僅需 2 次比較即完成查找，展現了二分查找的高效特性。

關鍵點總結

• 前提條件：數據必須有序
• 時間複雜度：O(log n)，遠優於線性查找的 O(n)
• 適用場景：靜態有序數據的頻繁查找
• 注意事項：mid 計算時若 low+high 可能溢出，建議用 low + (high - low) / 2