C 語言通用二分查找實現 (bsearch_int) 詳解

編輯：關於C語言

設計目標

專案中多處需二分查找，但數據型別不一 (int, float, 結構體...)。參考標準庫 bsearch 介面，實現一個**支援任意型別、可自定比較邏輯**的通用版本，並返回「插入位置」資訊 (類似 C++ lower_bound)，方便上層決定是否插入新元素。

介面設計

[c]
/**
 * @param key      要查找的鍵值指標
 * @param base     有序陣列基址
 * @param nmemb    元素個數
 * @param size     單個元素大小 (bytes)
 * @param piEqual  輸出參數：找到為 1，否則 0
 * @return         找到時返回索引；未找到時返回「應插入位置」索引 (0~nmemb)
 * @note           陣列必須按升序排列
 */
int bsearch_int(const void *key, const void *base, int nmemb, int size, int *piEqual);

核心演算法邏輯

維護左右邊界 l (inclusive) 和 u (exclusive)，初始 [0, nmemb)。
中點 idx = (l + u) / 2，取元素指標 p = base + idx * size。
比較 key 與 *p (此處針對 int 型別硬編碼比較，通用版應改為回調函數指標)。
相等：*piEqual=1，返回 idx。
key < mid：若 idx==0 直接返回 0；否再比較前一個元素 p2，若 key > *p2 返回 idx (插入位置)，否則縮小右邊界 u = idx。
key > mid：縮小左邊界 l = idx + 1。
循環結束返回 u (即 lower_bound 位置)。

完整代碼 (含註解)

[c]
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 = (const char *)base + idx * size;
        comparison = *(const int *)key - *(const int *)p;

        if (comparison == 0) {
            *piEqual = 1;
            return idx;
        } else if (comparison < 0) {
            if (idx == 0) return idx;
            p2 = (const char *)base + (idx - 1) * size;
            comparison2 = *(const int *)key - *(const int *)p2;
            if (comparison2 > 0) return idx; // 插在 idx-1 和 idx 之間
            u = idx;
        } else { // comparison > 0
            l = idx + 1;
        }
    }
    return u; // 未找到，返回插入位置
}

改進建議：真正的通用版

[c]
typedef int (*cmp_func_t)(const void *, const void *);

int bsearch_generic(const void *key, const void *base, size_t nmemb, size_t size,
                    cmp_func_t cmp, int *piEqual)
{
    size_t l = 0, u = nmemb, idx;
    *piEqual = 0;
    while (l < u) {
        idx = (l + u) / 2;
        const void *p = (const char *)base + idx * size;
        int c = cmp(key, p);
        if (c == 0) { *piEqual = 1; return idx; }
        else if (c < 0) u = idx;
        else l = idx + 1;
    }
    return u;
}

// 使用範例
int cmp_int(const void *a, const void *b) { return *(const int*)a - *(const int*)b; }
int cmp_str(const void *a, const void *b) { return strcmp(*(const char**)a, *(const char**)b); }