【C言語】bsearch関数の使い方

このページでは、C言語の標準関数である bsearch 関数の使い方について解説します。

この bsearch 関数の使い方に関しては、下記ページで紹介している qsort 関数の使い方に非常によく似ています。

【C言語】qsort関数の使い方

ですので、このページでは qsort 関数の使い方は理解されているものとし、その上で qsort 関数との違いに注目しながら bsearch 関数の使い方を解説させていただきたいと思います。

もし qsort 関数の使い方をご存知ない方は、事前に上記のページを確認してからこのページを読んでいただくことをオススメします。

後述でも解説しますが、そもそも bsearch 関数は qsort 関数とセットにして利用されることが多いので、bsearch 関数を使うのであれば qsort 関数についても知っておいた方が良いと思います。

bsearch 関数とは

それでは、まずは bsearch 関数がどのような関数であるのかについて解説します。

bsearch 関数は配列からデータを探索する関数

bsearch は、引数で指定したデータを配列の中から探索する関数です。

探索を行う際に用いられるアルゴリズムは「二分探索」です。二分探索はバイナリサーチとも呼ばれますので、bsearch の b を binary と考えると関数名が覚えやすいと思います。

二分探索がどのようなアルゴリズムであるかは下記ページで解説していますので、アルゴリズムを詳しく知りたい方は下記ページを読んでみてください。

【C言語】データの探索アルゴリズム（線形探索・二分探索）について解説

上のページを読んで見ていただければ分かると思いますが、二分探索を行うためにはそれなりに実装は必要ですし、実装するためには二分探索がどんなものであるかを理解しておかなければなりません。

ですが、bsearch 関数を利用すれば、わざわざ二分探索を自身でプログラミングしなくても、関数を呼び出すだけで二分探索によるデータの探索を実現することができます。

さらに、この bsearch 関数では、 qsort 関数と同様に、どんな型の配列であっても探索可能であるという特徴を持ちます。

整数の配列から特定の整数を探索することもできますし、文字列の配列から特定の文字列を探索することもできます。さらには、あなたが作成した構造体の配列でも探索することができてしまいます。

スポンサーリンク

bsearch 関数実行前にソートを行っておく必要あり

ただし、bsearch 関数には、関数実行前に事前に配列の各データをソートしておく必要があるという制約があります。そもそも二分探索もソート済みのデータからしか探索を行うことができません。

もちろん自身でソートを行うように実装しても良いのですが、qsort 関数を利用すれば簡単にソートを行うことが可能です（同様にソートを行う関数である heapsort や mergesort を利用しても良いです）。

比較関数を自作する必要あり

また、bsearch 関数では、これも qsort 関数と同様に、探索時に実行される “比較を行う関数（以降では比較関数と呼びます）” を作成し、その関数のアドレスを qsort 関数に渡してやる必要があります。

詳細に関しては後述で説明しますが、結論だけ書いておくと、この比較関数は qsort 関数で利用する比較関数と全く同じものが利用できます。

bsearch 関数の利用例

例えば下記では、int 型の配列 array の各データから 7 を探索する場合の bsearch 関数の利用例になります（比較関数は compare）。

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

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    printf("%d と %d の比較\n", *p_int1, *p_int2);

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    int i;

    int array[10] = {
        8, 1, 9, 6, 7, 3, 5, 0, 2, 4
    };
    
    int key;
    int *result;

    /* bsearch実行前にソート */
    printf("[ソート開始]\n");
    qsort(&array[0], 10, sizeof(array[0]), compare);
    
    /* 探索するデータを7に設定 */
    key = 7;
    printf("[探索開始]\n");
    result = bsearch(&key, &array[0], 10, sizeof(array[0]), compare);

    /* 探索結果を表示 */
    if (result != NULL) {
        printf("%dは配列の中に存在します\n", key);
        printf("%dはアドレス%pに存在します\n", key, result);
        printf("%dはソート後の配列の第%ld要素に存在します\n", key, result - &array[0]);
    } else {
        printf("%dは配列の中に存在しません\n", key);
    }

    return 0;
}

実行すると下記のように表示され、最後の３行から配列 array から 7 の探索結果が表示されていることが確認できると思います。

[ソート開始]
8 と 3 の比較
3 と 4 の比較
8 と 4 の比較
〜略〜
[探索開始]
7 と 5 の比較
7 と 8 の比較
7 と 7 の比較
7は配列の中に存在します
7はアドレス0x7ffeefbff47cに存在します
7はソート後の配列の第7要素に存在します

ちなみに後ろから２行目に表示されているアドレスは実行する PC によって変わると思います。

また最後の行では配列のどの要素に 7 が存在したかを表示していますが、ソート後の配列における要素番号が表示されている点に注意してください。

さらに、他の行の出力から比較関数 compare が何回も実行されていることと、配列 array のデータ（のアドレス）が比較関数 compare の引数として渡されていることが確認できると思います。

compare 関数は main 関数からは実行しておらず、前述の通り bsearch 関数（さらには qsort 関数）から実行されています。こんな感じで bsearch 関数を実行すると、比較関数を実行してデータの比較を行い、その比較結果に応じて探索が行われます。

大体 bsearch 関数の動作や比較関数との関係性は理解してもらえたのではないかと思いますので、ここからは個別に下記について解説していきたいと思います。

• bsearch 関数の使い方
• 比較関数の作り方

スポンサーリンク

bsearch 関数の使い方

それでは bsearch 関数の使い方（実行の仕方）について解説していきます。

bsearch 関数の定義

まず bsearch の関数定義は下記のようになります。

#include <stdlib.h>

void *bsearch(const void *key, const void *elems, size_t num_elem, size_t size_elem, int (* compar)(const void *, const void *));

まず bsearch 関数は stdlib.h で宣言されていますので、bsearch 関数を使用する際には stdlib.h を include する必要があります。

bsearch 関数の引数

bsearch 関数の各引数には下記を指定します。

• 第１引数 key：探索したいデータ（キー）のアドレス
• 第２引数 elems：探索を開始するデータのアドレス
• 第３引数 num_elem：探索対象のデータの数
• 第４引数 size_elem：探索対象の各データのサイズ（バイト）
• 第５引数 compare：比較関数のアドレス

上記の引数に対し、bsearch 関数では、アドレス elems から num_elem 個分のデータ（各データのサイズは size_elem）を探索対象として、key の指すデータの探索が実行されます。探索に必要な比較は compare の指す関数により行われます。

第１引数は探索したいデータ（以降ではキーと呼びます）の “アドレス” であることに注意が必要です。

また、bsearch 関数においては “探索対象” に関する引数、qsort 関数においては “ソート対象” に関する引数という違いはあるものの、 基本的に bsearch 関数の第２引数 〜 第５引数は、qsort 関数の第１引数 〜 第４引数とは同じ意味合いのものであると考えて良いです。

特に bsearch 関数を実行するためのソートを qsort 関数で実行する場合は、これらの引数は全く同じものを指定するので問題ありません。

スポンサーリンク

bsearch 関数の戻り値

また、bsearch 関数の戻り値は下記のようになります。

• 第２引数 elems から第１引数 key の指すデータが見つかった時：
  • 最初に見つかった elems のデータのアドレス
• 第２引数 elems から第１引数 key の指すデータが見つからなかった時：
  • NULL

bsearch 関数の戻り値の型は void * ですが、elems 内のデータのアドレスが返却されるわけですから、戻り値を受ける変数の型は elems に指定する変数の型に合わせて設定してやれば良いです。

例えば第２引数に int 型の配列を指定して bsearch 関数を実行するのであれば、bsearch 関数の戻り値のアドレスはその int 型の配列内のデータのものになりますので、戻り値を受け取る変数の型は int 型のデータを指す int * 型として変数宣言します。

ただ、あくまでも戻り値で得られるアドレスは、”ソート後” の配列内のデータのアドレスであり、”ソート前” の配列内のデータのアドレスではありません。つまり、bsearch 関数では、”ソート前” の配列のどの位置にキーが存在したかを特定することはできません。

bsearch 関数の基本的な使い方

ここまでの復習の意味も込めて、bsearch 関数の基本的な使い方を紹介していきたいと思います。

例えば、下記のような int 型の配列 array の中から  7 を bsearch 関数を使用して探索する場合について考えてみましょう。

int array[10];

配列名は array、配列のデータ数は 10、配列の型は int なので、bsearch 関数は下記のように実行することになります（比較関数の名前は compare としています）。

int main(void) {

    int array[10] = {
        10, 8, 3, 0, 16,
        8, 7, 32, 51, 99 
    };
    int key;
    int *ret;
    
    /* 事前にソートする */
    qsort(array, 10, sizeof(int), compare);

    /* 7を探索する */
    key = 7;
    ret = bsearch(&key, array, 10, sizeof(int), compare);

    /* 探索結果を表示 */
    if (ret != NULL) {
        printf("%dは配列内に存在します\n", *ret);
    } else {
        printf("%dは配列内に存在しません\n", key);
    }

    return 0;
}

この bsearch 関数を実行する際のポイントは４つです。

第１引数にはアドレスを指定する

まず探索する値は 7 ですが、数値の場合は変数に一旦格納し、その変数のアドレスを第１引数に指定する必要があります（文字列リテラルの場合はそのまま指定しても良い）。

今回は int 型の変数 key に 7 を格納し、bsearch 関数の第１引数には key のアドレス、つまり &key を指定するようにしています。

探索対象のデータはソートしておく必要あり

前述の通り、bsearch 関数を実行する前に、探索対象となるデータ（上記の場合はアドレス array から int 型のサイズのデータ 10 個分）は事前にソートしておく必要があります。そのため、上記では bsearch 関数実行前に qsort 関数を実行してソートを行っています。

探索結果は戻り値から判断する

また、bsearch 関数は探索結果を返却しますので、探索に成功したかどうかは bsearch 関数の戻り値から判断する必要があります。

上記では、bsearch 関数の戻り値を result に格納するようにしています。key が見つかった際には bsearch 関数は int 型の配列 array 内のアドレスを返却することになりますので、result の型は int * にするのが正しいです。

比較関数は qsort 関数と同じものを指定するので良い

さらに、bsearch 関数の第５引数と qsort 関数の第４引数には比較関数のアドレスを指定します。上記で両方で compare を指定している、つまり同じ関数のアドレスを指定しているように、基本的にはこの２つの引数に指定するアドレスの関数は同じもので良いです。

その理由については、次の比較関数の作り方で説明したいと思います。

関数実行時における bsearch 関数ならではのポイントは上記の４つくらいで、後は qsort 関数と同じです（構造体が指定できたり、特定の範囲のみを探索対象とできたりする点など）。

比較関数を含めた探索実行時のソースコードや、実際の探索結果などは、最後のbsearch 関数を利用した探索例で紹介させていただきたいと思います。

比較関数の作り方

続いて、bsearch 関数で使用する比較関数の作り方について解説していきたいと思います。

といっても、bsearch 関数で使用する比較関数と qsort 関数で使用する比較関数とでは役割は全く同じで、その役割は “ポインタ引数で渡される２つのデータの大小関係を比較し、その結果に応じた値を返却する” ことです。

作り方も同じですので、作り方自体についての詳細は下記ページの qsort 関数の解説ページを参考にしていただきたいです。

【C言語】qsort関数の使い方

ただ、実行される目的と戻り値の意味合いがちょっとだけ異なります（一応解説しますが、これも気にするほどのものではありません）。

ここでは、その bsearch 関数と qsort 関数とで使用する比較関数の違いと、両者で使用する比較関数が同じものであって良い理由についてのみ説明していきたいと思います。

スポンサーリンク

qsort 関数の比較関数とは実行される目的が違う

bsearch 関数と qsort 関数とで使用する比較関数は実行される目的が異なります。

bsearch 関数で使用する比較関数は、”探索” を進めるために実行されます。qsort 関数で使用する比較関数は、”ソート” を進めるために実行されます。

qsort 関数の比較関数とは戻り値の意味合いが違う

また、bsearch 関数と qsort 関数とで使用する比較関数では、戻り値の意味合いが若干異なります。

qsort 関数では、”実行後” のソート対象のデータを昇順ソートするか、もしくは降順ソートするかで戻り値を下記のように変更する必要がありました（第１引数のポインタが指すデータを “データ１”、第２引数のポインタが指すデータを “データ２” として説明しています）。

• 昇順ソートする場合
  • データ１ < データ２：0 より小さい値
  • データ１ > データ２：0 より大きい値
  • データ１ == データ２：0 
• 降順ソートする場合
  • データ１ < データ２：0 より大きい値
  • データ１ > データ２：0 より小さい値
  • データ１ == データ２：0 

その一方で、bsearch 関数では、”実行前” の探索対象のデータが昇順ソートされているか、もしくは降順ソートされているかで戻り値を下記のように変更する必要があります。

• 昇順ソートされている場合
  • データ１ < データ２：0 より小さい値
  • データ１ > データ２：0 より大きい値
  • データ１ == データ２：0 
• 降順ソートされている場合
  • データ１ < データ２：0 より大きい値
  • データ１ > データ２：0 より小さい値
  • データ１ == データ２：0 

要は、qsort 関数では、戻り値によって “実行後” のデータの並び方を指定するのに対し、bsearch 関数では、戻り値によって “実行前” のデータの並び方を指定することになります。

bsearch 関数で使用する比較関数で、ソートされている状態（降順 or 昇順）と食い違うような値を返却してしまうと正常に探索処理が行えないので注意してください。

例えば、昇順ソートされている探索対象のデータに対して、”降順ソートされている場合” の戻り値を返却するような比較関数を使用して bsearch 関数を実行してしまうと、正常に探索処理が行えません。

qsort 関数の比較関数と同じものを使用する

ということは、探索対象のデータを qsort 関数で “昇順ソート” した場合、すなわち比較関数で下記を戻り値とした場合、

• データ１ < データ２：0 より小さい値
• データ１ > データ２：0 より大きい値
• データ１ == データ２：0 

その次に実行する bsearch 関数では、探索対象のデータは “昇順ソート” されているのですから、下記を戻り値とした比較関数を使用する必要があることになります。

• データ１ < データ２：0 より小さい値
• データ１ > データ２：0 より大きい値
• データ１ == データ２：0 

つまり、qsort 関数と bsearch 関数とで使用する比較関数では、同じ値を返却するものにする必要があります。さらに、これらの比較関数では引数も役割も同じなので、結局はこれらの比較関数は同じものである必要があることになります。

今度は逆に、探索対象のデータを qsort 関数で “降順ソート” した場合、すなわち比較関数で下記を戻り値とした場合、

• データ１ < データ２：0 より大きい値
• データ１ > データ２：0 より小さい値
• データ１ == データ２：0 

その次に実行する bsearch 関数では、探索対象のデータは “降順ソート” されているのですから、下記を戻り値とした比較関数を使用する必要があります。

• データ１ < データ２：0 より大きい値
• データ１ > データ２：0 より小さい値
• データ１ == データ２：0 

こちらも昇順ソートの時と同様に、qsort 関数と bsearch 関数とでは同じ引数・同じ戻り値の比較関数を使用する必要があります。

つまり、qsort 関数で昇順 or 降順のどちらでソートを行ったにせよ、bsearch 関数では qsort 関数と同じ比較関数を使用する必要があります。ですので、基本的には bsearch 関数では qsort 関数と同じ比較関数を使用するので良いです（qsort 関数の第４引数に指定したものと同じものを、bsearch 関数の第５引数に指定する）。

同じ比較関数を使用する “必要がある” だけなので、もちろん bsearch 関数と qsort 関数とで異なる比較関数を使用するようにしても良いですが、それらの比較関数は同じ引数・同じ戻り値のものにする必要があるので、結局は同じ動作をする関数になると思います。

であれば、bsearch 関数と qsort 関数とで “同じ比較関数” を利用してやった方が、実装する関数の数も減るので楽です。

ただ、qsort 関数を利用せずに bsearch 関数を実行する場合は、bsearch 関数実行用に別途比較関数を作成する必要があります。この作り方は前述の通り qsort 関数の比較関数を作る時と全く同じですので、ここでの解説は省略させていただきます。

スポンサーリンク

bsearch 関数を利用した探索例

最後に bsearch 関数を利用した探索例となるソースコードをいくつか紹介していきたいと思います。

比較関数をどう作っているかは qsort 関数の解説ページで説明していますので、特に下記ページの qsort 関数を利用したソート例を読んでみていただければと思います。

【C言語】qsort関数の使い方

整数を bsearch 関数で探索する

まずは一番基本的な整数（int 型）を bsearch 関数で探索する例を示していきたいと思います。

ソート後に配列から探索する

下記は qsort 関数で配列 array をソートした後、bsearch 関数で配列 array の中から 21 を探索する例になります。

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

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    int array[10] = {
        8, 19, 45, 23, 59, 21, 56, 10, 89, 10
    };
    int *result;
    int key;

    /* bsearch実行前にソート */
    qsort(array, 10, sizeof(int), compare);

    /* 21を探索 */
    key = 21;
    result = bsearch(&key, array, 10, sizeof(int), compare);

    /* 探索結果を表示 */
    if (result != NULL) {
        printf("%dは配列の中に存在します\n", key);
        printf("%dはアドレス%pに存在します\n", key, result);
        printf("%dはソート後の配列の第%ld要素に存在します\n", key, result - &array[0]);
    } else {
        printf("%dは配列の中に存在しません\n", key);
    }

    return 0;
}

上記のように bsearch 関数を実行すると、array[0] 〜 array[9] の中から値  21 の探索が行われます。今回は array の中に 21 が存在しますので探索に成功し、下記のような結果が表示されることになります。

21は配列の中に存在します
21はアドレス0x7ffeefbff470に存在します
21はソート後の配列の第4要素に存在します

２行目のアドレスの値は、実行する環境やタイミングによって異なると思います。

３行目の表示は array[4] に 21 が存在したことを示しています。array は事前に qsort によりソートされていますので、ソート後の並びにおいて、array の第 4 要素に 21 が存在したことを示すことになります（21 は array の中で５番目に大きい値なので、昇順ソート後は array[4] に移動している）。

また、bsearch 関数と qsort 関数では比較関数に同じ compare を使用しています。

既にソートされている配列から探索する

既に配列がソートされている場合は、再度ソートを行わなくても、そのまま bsearch を実行してソートを行うことが可能です。

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

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    int array[10] = {
        8, 10, 10, 19, 21, 23, 45, 56, 59, 89
    };
    int *result;
    int key;

    /* 21を探索 */
    key = 21;
    result = bsearch(&key, array, 10, sizeof(int), compare);

    /* 探索結果を表示 */
    if (result != NULL) {
        printf("%dは配列の中に存在します\n", key);
        printf("%dはアドレス%pに存在します\n", key, result);
        printf("%dはソート後の配列の第%ld要素に存在します\n", key, result - &array[0]);
    } else {
        printf("%dは配列の中に存在しません\n", key);
    }

    return 0;
}

array は初期化時に昇順ソートされた状態になるので、qsort 関数を実行せずに bsearch 関数を実行しても、ソート後に配列から探索するの時と同様の結果を得ることができます。

ただし、bsearch 関数に指定する compare では、探索対象のデータが “昇順ソート” されていることを考慮して値を返却する必要があります（詳細は qsort 関数の比較関数とは戻り値の意味合いが違うで解説しています）。

ソートされていない配列から探索する（NG）

ではソートされていない配列から探索を行うとどうなるでしょうか？下記はソート後に配列から探索するで紹介したソースコードから qsort 関数の実行部分のみを削除したものになります。

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

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    int array[10] = {
        8, 19, 45, 23, 59, 21, 56, 10, 89, 10
    };
    int *result;
    int key;

    /* 21を探索 */
    key = 21;
    result = bsearch(&key, array, 10, sizeof(int), compare);

    /* 探索結果を表示 */
    if (result != NULL) {
        printf("%dは配列の中に存在します\n", key);
        printf("%dはアドレス%pに存在します\n", key, result);
        printf("%dはソート後の配列の第%ld要素に存在します\n", key, result - &array[0]);
    } else {
        printf("%dは配列の中に存在しません\n", key);
    }

    return 0;
}

この場合、実は探索に成功してしまいます…。二分探索では、まず配列の中央のデータがキーと一致するかを判断しますが、21 もちょうど配列の中央に存在するので（array[10 / 2] に存在する）、たまたま 21 は探索に成功します。

ただし、10 などを探索した場合は探索に失敗して下記のように表示されます。

10は配列の中に存在しません

たまたま探索に成功することもありますが、基本的にはソートせずに bsearch 関数を実行すると正常に探索は行われないと考えて利用した方が良いです。

異なる比較関数を利用して探索する（NG）

今度は qsort 関数と bsearch 関数とで異なる比較関数を利用する例を紹介します。qsort 関数では compare_sort を、bsearch 関数では compare_search を利用するようにし、それぞれの比較関数では戻り値が異なるようにしています。

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

/* 比較関数 */
int compare_sort(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}

int compare_search(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = 1;
    } else if (*p_int1 > *p_int2) {
        ret = -1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    /* bsearch実行前にソート */
    int array[10] = {
        8, 19, 45, 23, 59, 21, 56, 10, 89, 10
    };
    int *result;
    int key;

    qsort(array, 10, sizeof(int), compare_sort);
    
    /* 21を探索 */
    key = 21;
    result = bsearch(&key, array, 10, sizeof(int), compare_search);

    /* 探索結果を表示 */
    if (result != NULL) {
        printf("%dは配列の中に存在します\n", key);
        printf("%dはアドレス%pに存在します\n", key, result);
        printf("%dはソート後の配列の第%ld要素に存在します\n", key, result - &array[0]);
    } else {
        printf("%dは配列の中に存在しません\n", key);
    }

    return 0;
}

この場合は、探索に失敗します（もちろんキーによっては前述のようにたまたま成功することもありますが…）。

今回は意図的に bsearch と qsort で使用する比較関数の戻り値を異なるものにしていますが、異なる比較関数を用意するとケアレスミス等でお互いの比較関数の戻り値に食い違いが発生する可能性がありますので、同じ比較関数を利用した方が無難だと思います。

複数存在するキーを探索する

整数の探索の最後の例として、配列内にキーが複数存在する場合の探索例を紹介します。

下記はソート後に配列から探索するで紹介したソースコードを、10 を探索するように変更したものになります（10 は array に２つ存在する）。

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

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 < *p_int2) {
        ret = -1;
    } else if (*p_int1 > *p_int2) {
        ret = 1;
    } else {
        ret = 0;
    }

    return ret;

}


int main(void) {

    int array[10] = {
        8, 19, 45, 23, 59, 21, 56, 10, 89, 10
    };
    int *result;
    int key;

    /* bsearch実行前にソート */
    qsort(array, 10, sizeof(int), compare);

    /* 10を探索 */
    key = 10;
    result = bsearch(&key, array, 10, sizeof(int), compare);

    /* 探索結果を表示 */
    if (result != NULL) {
        printf("%dは配列の中に存在します\n", key);
        printf("%dはアドレス%pに存在します\n", key, result);
        printf("%dはソート後の配列の第%ld要素に存在します\n", key, result - &array[0]);
    } else {
        printf("%dは配列の中に存在しません\n", key);
    }

    return 0;
}

実行すると、下記のような結果が表示されます。

10は配列の中に存在します
10はアドレス0x7ffeefbff468に存在します
10はソート後の配列の第2要素に存在します

array には２つの 10 が存在しており、qsort 実行後の並びにおいては array[1] と array[2] が 10 になります。このように、キーが複数存在する場合、bsearch 関数は最初に見つけたキーのアドレスを返却します。また、最初に見つかるのは必ずしも配列の前側に存在するものになるとは限らないので注意してください（これは二分探索がデータを二分しながら探索するアルゴリズムだからです）。

文字列を bsearch 関数で探索する

次は文字列を bsearch 関数で探索する例を紹介します。ここでは上手く探索できる例のみを示しますが、bsearch 関数の実行の仕方などによって整数を bsearch 関数で探索するで示した時と同様の動きになりますので注意してください（例えばソートされていない配列から探索する（NG）で説明したようにソートせずに探索すると基本的に探索に失敗します）。

下記は文字列の配列 array から bsearch 関数を利用して "Saturday" を探索する例になります。

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* strcmp, strcpy */

int compare(const void *p_data1, const void *p_data2) {
    const char *p_str1 = p_data1;
    const char *p_str2 = p_data2;

    return strcmp(p_str1, p_str2);
}


int main(void) {

    char array[7][256] = {
        "Sunday",
        "Monday",
        "Tuesday",
        "Wednesday",
        "Thursday",
        "Friday",
        "Saturday"
    };

    char key[256];
    char *result;

    /* 事前にqsortでソート */
    qsort(&array[0][0], 7, sizeof(array[0]), compare);
    
    /* "Saturday"を探索 */
    strcpy(key, "Saturday");
    result = bsearch(key, &array[0][0], 7, sizeof(array[0]), compare);

    if (result != NULL) {
        printf("%sは配列内に存在します\n", result);
    } else {
        printf("%sは配列内に存在しません\n", key);
    }
    return 0;
}

まず、文字列を探索するのですから、bsearch 関数の第１引数には文字列を指定する必要があります。

また、bsearch 関数の戻り値を受け取る変数の型（上記の場合は result の型）は char * 型にする必要があります。

これは、bsearch 関数が返却するのがソート対象である配列 array 内の１つのデータのアドレスだからです。array 内の各データの型は char ですので、bsearch 関数の戻り値を受け取る変数の型は char * とする必要があります。

スポンサーリンク

構造体を bsearch 関数で探索する

bsearch により構造体のデータを探索することも可能です。下記は構造体 PERSON の配列 people から、age メンバが 20 のデータを探索する例になります。

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* strcpy */

/* データの個数 */
#define NUM_PEOPLE 10

/* 名前の配列 */
char *names[] = {
    "ichiro", "jiro", "saburo", "shiro", "goro",
    "rokuro", "nanaro", "hachiro", "kuro", "zyuro"
};

typedef struct _PERSON {
    int age;
    int weight;
    int height;
    char name[256];
} PERSON;


static int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const PERSON *person1 = p_data1;
    const PERSON *person2 = p_data2;

    if (person1->age < person2->age) {
        ret = -1;
    } else if (person1->age > person2->age) {
        ret = 1;
    } else {
        ret = 0;
    }
    return ret;
}

void init(PERSON *people, int num) {
    int i;

    for (i = 0; i < num; i++) {
        /* 乱数を使って適当に初期化 */
        people[i].age = 10 * (i + 1);
        people[i].weight = rand() % 50 + 50;
        people[i].height = rand() % 100 + 100;
        strcpy(people[i].name, names[rand() % 10]);
    }
}

void print(PERSON *people, int num) {
    int i;

    for (i = 0; i < num; i++) {
        printf("people[%d]:\n", i);
        printf("  age    = %d\n", people[i].age);
        printf("  weight = %d\n", people[i].weight);
        printf("  height = %d\n", people[i].height);
        printf("  name   = %s\n", people[i].name);
    }
}

int main(void) {

    PERSON people[NUM_PEOPLE];
    int key;
    PERSON *result;

    init(people, NUM_PEOPLE);

    /* age に対してソート */
    qsort(people, NUM_PEOPLE, sizeof(people[0]), compare);

    /* ソート結果を一旦表示 */
    print(people, NUM_PEOPLE);
    
    /* ageが20の構造体を探索 */
    key = 20;
    result = bsearch(&key, people, NUM_PEOPLE, sizeof(people[0]), compare);

    if (result != NULL) {
        printf("歳が%dなのは%sです\n", key, result->name);
    } else {
        printf("歳が%dの人はいません\n", key);
    }


    return 0;
}

ポイントは２つです。

１つ目は bsearch 関数の戻り値を受け取る変数の型（上記の場合は result の型）です。bsearch 関数が返却するのはソート対象である配列 people 内の１つのデータのアドレスとなります。

people 内の各データの型は PERSON ですので、bsearch 関数の戻り値を受け取る変数の型は PERSON * とする必要があります。

２つ目は bsearch 関数の前に実行する qsort 関数では、bsearch 関数での探索先になるメンバに対してソートを行う必要があることです。上記では bsearch 関数で age メンバが 20 のものを探索したかったので、qsort 関数では age メンバに対してソートを行うようにしています。

どのメンバに対してソートを行うかは比較関数によって決まりますので、比較関数では age メンバの大小関係に応じた値を返却する必要があります。

まとめ

このページでは、C言語の標準関数である bsearch 関数の使い方について解説しました！

基本的な使い方は qsort 関数に非常によく似ているので、どちらか一方の使い方を覚えておくと良いと思います（bsearch 関数の場合はキーを指定する分、引数が１つ多いことに注意が必要ですが）。

また、bsearch 関数を実行するためには事前に探索対象のデータをソートしておく必要がある点には注意してください。bsearch 関数を利用した探索例でも例を紹介した通り、ソートせずに bsearch 関数を実行すると正常に探索を行うことができません。

bsearch 関数自体は、二分探索で高速に探索ができるのですが、事前にソートしておかなければならないのが欠点ですね…。”ソートの処理時間 + 二分探索の処理時間” は、基本的に “線形探索の処理時間” よりも長いです。これはソートを行う時間が長いからです。

bsearch 関数が本領発揮できるのは、常にソートされている配列から探索を行うような場面です。わざわざ事前にソートを行わなければならないような配列に対して探索する場合には、線形探索した方が早いです。

その線形探索に関しても、C言語の標準関数として lfind 関数が用意されています。この lfind 関数に関しては下記ページで解説していますので、lfind 関数を使って見たい方は是非読んでみてください（bsearch の使い方とほとんど変わらないです）！

【C言語】lfind関数の使い方