C語言二分查找演算法實作詳解

二分查找演算法核心概念

當我們有一個已按升序排列的陣列，需要快速定位特定元素位置時，二分查找是最經典且高效的解決方案。本文透過完整的 C 語言程式碼範例，詳細解析二分查找的運作邏輯與實作細節。

完整程式碼實作

#include <stdio.h>

int binsearch(int x, int v[], int n);

int main() {
    int i, result, n;
    int wait;
    int x = 17;  // 要查找的目標值
    int v[20];   // 定義包含 20 個元素的陣列
    
    // 為陣列賦值 0~19
    for(i = 0; i < 20; ++i)
        v[i] = i;
    
    n = 20;
    result = binsearch(x, v, n);
    printf("查找結果索引: %d\n", result);
    scanf("%d", &wait);
    return 0;
}

int binsearch(int x, int v[], int n) {
    int low, high, mid;
    low = 0;
    high = n - 1;
    
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else {
            // 除錯輸出：觀察循環執行狀態
            printf("mid = %d, low = %d, high = %d\n", mid, low, high);
            return mid;  // 找到目標，返回索引
        }
    }
    return -1;  // 未找到
}

演算法邏輯深度解析

二分查找的核心思想是分治法：每次將搜尋範圍縮減一半。

1. 初始化：low 指向陣列起始索引 0，high 指向最後一個索引 n-1
2. 計算中點：mid = (low + high) / 2
3. 比較判斷：
   • 若目標值 x 小於 v[mid]，說明目標在左半部，high = mid - 1
   • 若目標值 x 大於 v[mid]，說明目標在右半部，low = mid + 1
   • 若相等，直接返回 mid 索引
4. 循環終止條件：當 low > high 時，表示搜尋區間為空，返回 -1 代表未找到

時間複雜度優勢

二分查找的時間複雜度為 O(log n)，對於 20 個元素最多只需 5 次比較（log₂20 ≈ 4.32），而線性查找最多需 20 次。資料量越大，優勢越明顯。

常見陷阱與注意事項

• 陣列必須有序：前提條件是陣列已按升序排列
• 索引溢出風險：大型陣列時 (low + high) 可能溢出，建議改用 mid = low + (high - low) / 2
• 邊界條件：while 條件用 <= 而非 <，確保單元素陣列也能正確處理

除錯觀察技巧

程式碼中保留的 printf 除錯輸出可幫助理解每輪循環的 low、mid、high 變化，建議初學者實際執行觀察，加深對演算法流程的理解。