C語言通用二分查找算法實現詳解

二分查找是處理有序數據集的經典算法，時間複雜度 O(log n)。本文提供一個通用的 C 語言實現，支援任意資料類型，適合在專案中複用，避免重複造輪子。

設計思路

• 使用 void* 泛型指標支援任意類型
• 透過 size 參數計算元素位址
• 回傳找到的索引，或插入位置
• piEqual 標記是否精確匹配

完整實現代碼

int bsearch_int(const void *key, const void *base, int nmemb, int size, int *piEqual)
{
    size_t l, u, idx;
    const void *p, *p2;
    int comparison, comparison2;

    *piEqual = 0;
    if (nmemb < 0) return -1;
    if (!nmemb) return 0;
    
    l = 0;
    u = nmemb;

    while (l < u) {
        idx = (l + u) / 2;
        p = (void *)(((const char *)base) + (idx * size));
        comparison = *(int *)key - *(int *)p;

        if (comparison == 0) {
            *piEqual = 1;
            return idx;
        } else if (comparison < 0) {
            if (idx == 0) return idx;
            p2 = (void *)(((const char *)base) + ((idx - 1) * size));
            comparison2 = *(int *)key - *(int *)p2;
            if (comparison2 > 0) return idx;
            u = idx;
        } else { /* comparison > 0 */
            l = idx + 1;
        }
    }
    return u;
}

關鍵點解析

1. 泛型指標運算

p = (void *)(((const char *)base) + (idx * size));

將 base 轉為 char* 按位元組偏移，再轉回 void*，實現任意類型的位址計算。

2. 邊界條件處理

• idx == 0 時直接回傳，避免 idx - 1 下溢
• 迴圈條件 l < u 確保收斂

3. 回傳值語義

使用範例

int arr[] = {10, 20, 30, 40, 50};
int key = 30;
int equal;
int idx = bsearch_int(&key, arr, 5, sizeof(int), &equal);
// idx = 2, equal = 1

int key2 = 25;
int idx2 = bsearch_int(&key2, arr, 5, sizeof(int), &equal);
// idx2 = 2 (插入位置), equal = 0

擴展建議

• 加入比較函式指標 int (*cmp)(const void*, const void*) 完全泛型化
• 支援 bsearch 標準庫相容介面
• 加入遞迴版本供教學參考