C言語編 標準ライブラリのリファレンス bsearch

先頭へ戻る

bsearch関数

概要 配列から要素をサーチする。
ヘッダ stdlib.h
形式 void* bsearch(const void* key, void* base, size_t count, size_t size, int (*compar)(const void* key, const void* value));
引数 key 発見したい値へのポインタ。
base サーチ対象の配列を指すポインタ。
この配列は、昇順にソートされていなければならない。
count サーチ対象の配列の要素数。
0 を指定した場合は何もせず、何も発見されない。
size 要素1つの大きさ。
compar 要素の大小関係を比較する関数(以下、比較用関数)へのポインタ。
比較用関数の第1引数(key)は、bsearch関数の引数key に渡したポインタであり、第2引数(value) はサーチ対象の配列内にある要素を指すポインタである。key が指す値が、value が指す値よりも小さいときは 0 未満の値を、同じときは 0 を、大きいとは 1 以上の値を返すように実装する。
戻り値 引数key が指し示す値と一致する要素があれば、その要素へのポインタを返す。なければヌルポインタが返される。一致する要素が複数個ある場合、どの要素へのポインタが返されるかは、未規定である。
詳細 引数base が指す配列から目的の値をサーチする。一般に、二分探索(アルゴリズムとデータ構造編【探索】第4章)によって実装されるため、サーチ対象の配列はソート済みであることが要求される。またソート順序は、昇順でなければならない。ソートは例えば、qsort関数で行える。
サーチしたい値は、引数key によって指し示す形で提供する。また、配列内の各要素の値との大小関係の比較のために、比較用関数を外部で定義し、この関数へのポインタを渡す。
注意 比較用関数の中で、サーチ対象の配列を書き換えてはならない。
使用例
#include <stdio.h>
#include <stdlib.h>

#define SIZE_OF_ARRAY(array)	(sizeof(array)/sizeof(array[0]))

int compareInt(const void* a, const void* b);

int main(void)
{
    int table[] = { 66, 85, 70, 92, 61, 89 };
    char str[40];
    int target;
    int* search_result;


    /* bsearch関数を使う前には、対象データがソート済みでなければならないので、
       事前に qsort関数でソートしておく 
    */
    qsort( table, SIZE_OF_ARRAY(table), sizeof(int), compareInt );


    puts( "サーチする値を入力してください。" );
    fgets( str, sizeof(str), stdin );
    sscanf( str, "%d", &target );

    /* サーチ */
    search_result = bsearch( &target, table, SIZE_OF_ARRAY(table), sizeof(int), compareInt );
    if( search_result == NULL ){
        printf( "%d は存在しません。\n", target );
    }
    else{
        printf( "%d を発見しました。\n", target );
    }

    return 0;
}

/*
    int型による順序比較。

    引数:
        a:	比較する要素。
        b:	比較する要素。
    戻り値:
        a の方が小さいとき負数、
        b の方が小さいとき 0 より大きい値、
        a と b が同じときは 0、
         が返される。
*/
int compareInt(const void* a, const void* b)
{
    int aNum = *(const int*)a;
    int bNum = *(const int*)b;

    if( aNum < bNum ){
        return -1;
    }
    else if( aNum > bNum ){
        return 1;
    }
    return 0;
}

実行結果:

サーチする値を入力してください。
70
70 を発見しました。
関連 事前に配列を昇順にソートしておかなければならないが、その作業には qsort関数が利用できる。
解説章 第38章


参考リンク



更新履歴

'2018/4/20 「NULL」という表記を「ヌルポインタ」に修正。

'2018/4/5 全体的に記述を見直して修正。

'2018/2/22 「サイズ」という表記について表現を統一。 型のサイズ(バイト数)を表しているところは「大きさ」、要素数を表しているところは「要素数」。

'2018/1/22 新規作成。



標準ライブラリのリファレンス(名前順)のトップページへ

標準ライブラリのリファレンス(ヘッダ別)のトップページへ

C言語編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー