C言語のbsearchでソート済み配列を高速検索する方法を解説

2025年10月25日

C言語

アルゴリズムを自作せずに、標準ライブラリだけでソート済み配列から要素を高速に探すならbsearchが便利です。

探索は二分探索で行われ、配列サイズが大きくても効率よく動作します。

本記事では、bsearchの役割や使い方、比較関数の書き方、実用的なサンプルに加えて、初心者がつまずきやすいポイントを丁寧に解説します。

目次 [ close ]

bsearchでソート済み配列を高速検索

bsearchの役割とメリット

bsearchは標準ライブラリ(#include <stdlib.h>)が提供する二分探索関数で、配列内の要素をO(log n)で検索できます。

配列が大きくなるほど線形探索(O(n))との差は大きくなり、実行時間の削減につながります。

自力で二分探索を実装するよりもコード量が少なく、バグを生みにくいのも大きな利点です。

探索対象は任意の型でかまいません。

関数ポインタで渡す比較関数次第で、整数・浮動小数・構造体・文字列などに対応できます。

戻り値は見つかった要素のポインタなので、見つかった位置のインデックス計算も容易です。

使う前提: 配列はソート済み

bsearchは「配列がソート済みである」ことを前提に動作します。

未ソートの配列に対して使うと、結果は未定義です。

並べ替えには標準ライブラリのqsortが使えますが、ソートに使う比較関数と検索に使う比較関数を必ず一致させてください。

並べ替えの順序(昇順・降順、文字列の大小関係など)が一致していないと、正しく見つかりません。

bsearchの使い方と引数

関数プロトタイプ

以下が標準的なプロトタイプです。

比較関数comparの引数はconst void *で、要素型にキャストして使います。

C言語

#include <stdlib.h>

/* 二分探索: key を base から始まる配列内で探す */
void *bsearch(const void *key,
              const void *base,
              size_t nmemb,
              size_t size,
              int (*compar)(const void *, const void *));

引数(base, nmemb, size, compar)の意味

bsearchは5つの引数を取ります。

ここでは特に混乱しやすいbase、nmemb、size、comparを中心に説明します(最初のkeyは「探したい値」へのポインタです)。

base: 配列の先頭アドレスです。例えばint a[]ならaを渡します。
nmemb: 配列の要素数です。静的配列ならsizeof(a) / sizeof(a[0])で安全に求められます。
size: 1要素のサイズ(バイト数)です。sizeof(a[0])を使うのが安全です。
compar: 比較関数です。2つの要素(または要素とキー)を比較し、負・0・正を返します。

次の表は、よく使う指定例のまとめです。

引数	意味	よく使う指定例
key	探したい値のアドレス	`&key`、文字列配列なら`&keyStr`
base	配列先頭	`a`
nmemb	要素数	`sizeof(a)/sizeof(a[0])`
size	要素サイズ	`sizeof(a[0])`
compar	比較関数	`cmp_int`、`cmp_str` など

戻り値

戻り値は一致した要素へのポインタです。

見つからなければNULLが返ります。

配列の要素型にキャストして使います。

インデックスが必要な場合は、(found - array)のようにポインタ差を取ります。

なお重複要素がある場合、どれが返るかは未規定です。

比較関数の書き方

比較関数は「lhsが小さいなら負、等しいなら0、大きいなら正」を返すという規約を守り、ソート順と一致する定義にしてください。

整数の比較関数(安全版)

引き算による比較はオーバーフローの危険があるため避け、大小比較で書きます。

C言語

/* 昇順: a < b なら負、a == b なら 0、a > b なら正 */
static int cmp_int(const void *a, const void *b) {
    int lhs = *(const int *)a;
    int rhs = *(const int *)b;

    /* (lhs > rhs) は 1/0、(lhs < rhs) は 1/0。
       差を取ると -1/0/1 のいずれかになる。 */
    return (lhs > rhs) - (lhs < rhs);
}

文字列の比較関数

文字列配列(const char *の配列)では、「要素」はchar *なので、比較関数は「char *へのポインタ」(char **)を受け取る点に注意します。

C言語

#include <string.h>

/* 昇順の辞書順で比較 */
static int cmp_str(const void *a, const void *b) {
    const char *const *sa = (const char *const *)a; /* a は要素へのポインタのアドレス */
    const char *const *sb = (const char *const *)b;
    return strcmp(*sa, *sb);
}

降順にしたい場合

比較の符号を反転するか、引数を入れ替えます。

例

return -cmp_int(a, b);。

この降順でソートした配列を検索する場合も、同じ降順の比較関数をbsearchに渡します。

サンプルコードで学ぶ

int配列を検索する最小例

昇順に並んだint配列から、存在する値と存在しない値を探す最小例です。

C言語

#include <stdio.h>
#include <stdlib.h>

/* int の昇順比較(オーバーフロー安全) */
static int cmp_int(const void *a, const void *b) {
    int lhs = *(const int *)a;
    int rhs = *(const int *)b;
    return (lhs > rhs) - (lhs < rhs); /* -1, 0, 1 を返す */
}

int main(void) {
    /* すでに昇順にソート済みとする */
    int arr[] = {1, 4, 7, 10, 14, 21};
    size_t n = sizeof(arr) / sizeof(arr[0]);

    int key1 = 10; /* 存在するキー */
    int key2 = 8;  /* 存在しないキー */

    /* 見つかった場合は要素へのポインタ、見つからなければ NULL */
    int *found1 = bsearch(&key1, arr, n, sizeof(arr[0]), cmp_int);
    int *found2 = bsearch(&key2, arr, n, sizeof(arr[0]), cmp_int);

    if (found1 != NULL) {
        size_t idx = (size_t)(found1 - arr); /* インデックスを計算 */
        printf("key %d found at index %zu (value=%d)\n", key1, idx, *found1);
    } else {
        printf("key %d not found\n", key1);
    }

    if (found2 != NULL) {
        size_t idx = (size_t)(found2 - arr);
        printf("key %d found at index %zu (value=%d)\n", key2, idx, *found2);
    } else {
        printf("key %d not found\n", key2);
    }

    return 0;
}

実行結果

key 10 found at index 3 (value=10)
key 8 not found

文字列配列を検索する例

文字列配列は「ポインタの配列」なので、比較関数でのキャストに注意します。

ここではqsortでソートしてからbsearchで検索します。

C言語

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 文字列(辞書順・昇順)の比較関数 */
static int cmp_str(const void *a, const void *b) {
    const char *const *sa = (const char *const *)a;
    const char *const *sb = (const char *const *)b;
    return strcmp(*sa, *sb);
}

int main(void) {
    const char *words[] = {"banana", "apple", "cherry", "date"};
    size_t n = sizeof(words) / sizeof(words[0]);

    /* 使う前提: ソート済み。qsort で並べ替える */
    qsort(words, n, sizeof(words[0]), cmp_str);

    /* 探すキーは「文字列へのポインタ」。
       bsearch の key は「要素と同じ型のオブジェクトへのポインタ」なので、
       const char * key を &key (const char **) として渡す。 */
    const char *key1 = "cherry";
    const char *key2 = "orange";

    const char **found1 = bsearch(&key1, words, n, sizeof(words[0]), cmp_str);
    const char **found2 = bsearch(&key2, words, n, sizeof(words[0]), cmp_str);

    /* 並べ替え後の配列を確認 */
    printf("sorted: ");
    for (size_t i = 0; i < n; ++i) {
        printf("%s%s", words[i], (i + 1 < n) ? ", " : "\n");
    }

    if (found1 != NULL) {
        size_t idx = (size_t)(found1 - words);
        printf("\"%s\" found at index %zu\n", *found1, idx);
    } else {
        printf("\"%s\" not found\n", key1);
    }

    if (found2 != NULL) {
        size_t idx = (size_t)(found2 - words);
        printf("\"%s\" found at index %zu\n", *found2, idx);
    } else {
        printf("\"%s\" not found\n", key2);
    }

    return 0;
}

実行結果

sorted: apple, banana, cherry, date
"cherry" found at index 2
"orange" not found

よくあるエラーと対策

ソート順と比較関数の不一致

配列を昇順でソートしたのに、bsearchには降順比較関数を渡してしまうなど、ソート順と比較関数の不一致は最頻出のミスです。

結果がNULLになったり、誤った要素を指す原因になります。

対策はソートと検索で同じ比較関数を使い回すことです。

例

下降順で統一したいなら、qsortにもbsearchにもcmp_descを渡します。

C言語

/* 降順比較の例 (int) */
static int cmp_int_desc(const void *a, const void *b) {
    int lhs = *(const int *)a, rhs = *(const int *)b;
    return (rhs > lhs) - (rhs < lhs); /* 逆順 */
}

sizeはsizeofで正しく指定

1要素のサイズsizeをリテラルで書かないでください。

環境依存でサイズが変わるため、動作が壊れます。

常にsizeof(array[0])またはsizeof *arrayを使います。

悪い例

sizeof(int)を決め打ち、4と書く良い例: sizeof(arr[0])、sizeof(words[0])

keyの渡し方(アドレス)を間違えない

keyは「要素と同じ型のオブジェクトへのポインタ」です。

整数なら&key、文字列配列ならポインタへのポインタとして&keyStrを渡します。

よくある誤りは、文字列配列でkeyStr自体(=文字列先頭)をそのまま渡してしまうケースです。

悪い例(文字列配列): bsearch(keyStr, words, ...) 良い例(文字列配列): bsearch(&keyStr, words, ...)

戻り値のNULLチェックを忘れない

見つからない場合はNULLです。

すぐにデリファレンスすると未定義動作を招きます。

必ずif (found != NULL)で分岐してから使います。

C言語

int *found = bsearch(&key, arr, n, sizeof(arr[0]), cmp_int);
if (found != NULL) {
    /* OK: found を使う */
} else {
    /* 見つからなかった場合の処理 */
}

比較関数で引き算比較は避ける

次のような比較は、オーバーフローで誤判定になる恐れがあります。

C言語

/* 悪い例: a が INT_MIN, b が INT_MAX のときに破綻しうる */
static int bad_cmp_int(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b; /* オーバーフローの危険 */
}

大小比較で書けば安全です。

C言語

/* 良い例 */
static int good_cmp_int(const void *a, const void *b) {
    int lhs = *(const int *)a, rhs = *(const int *)b;
    return (lhs > rhs) - (lhs < rhs);
}