基礎演算法教學：二分搜尋法（Binary Search）C 語言完整實作

基礎演算法教學：二分搜尋法（Binary Search）C 語言完整實作

二分搜尋（折半搜尋）是針對已排序陣列的高效查找演算法，時間複雜度 O(log n)。本文詳細說明前置條件、核心邏輯、C 語言實作細節與常見錯誤，並提供可直接編譯執行的完整程式碼。

兩大前置條件

1. 資料必須有序（遞增或遞減）
2. 必須使用循序儲存結構（陣列），支援隨機存取

核心邏輯

low = 0, high = n-1
while (low <= high) {
    mid = (low + high) / 2
    if (key == a[mid]) 找到，返回
    else if (key < a[mid]) high = mid - 1  // 搜尋左半
    else low = mid + 1                     // 搜尋右半
}
未找到，返回 -1

完整 C 程式碼

#include <stdio.h>

int binary_search(const int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2; // 防溢位寫法
        if (arr[mid] == key) return mid;
        else if (arr[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

void display_result(int idx, const int original[], int n, int key) {
    if (idx != -1) {
        // 找在原始陣列中的位置（若有重複值會找到第一個）
        for (int i = 0; i < n; i++)
            if (original[i] == key) { printf("所在位置：%d\n", i); break; }
    } else {
        printf("對不起，找不到該數值\n");
    }
}

int main() {
    int a[] = {15, 8, 100, 46, 22, 56, 34, 79, 98, 66, 200, 11, 300};
    int n = sizeof(a) / sizeof(int);
    int b[n]; // 複製排序用
    for (int i = 0; i < n; i++) b[i] = a[i];

    // 簡單氣泡排序（教學用，實務建議 qsort）
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (b[i] > b[j]) { int t=b[i]; b[i]=b[j]; b[j]=t; }

    int key;
    printf("請輸入要查找的整數：");
    scanf("%d", &key);

    int pos = binary_search(b, 0, n-1, key);
    display_result(pos, a, n, key);
    return 0;
}

關鍵實作細節

• mid 計算：用 low + (high - low)/2 避免 low+high 溢位
• const 正確性：const int arr[] 承諾不修改陣列
• 返回索引而非值：更具通用性，呼叫端可自行取值
• 排序獨立：搜尋函數不負責排序，遵循單一職責原則

測試案例

輸入：200  → 輸出：所在位置：10
輸入：500  → 輸出：對不起，找不到該數值

延伸應用

• 尋找第一個/最後一個滿足條件的元素（下界/上界）
• 在單調函數上二分答案（如 sqrt 整數解）
• C++ STL lower_bound/upper_bound 即此思想

二分搜尋是演算法面試必考、工程實戰高頻工具，徹底掌握其邊界條件與變體寫法，能大幅提升解決問題的效率。