≫ ホーム ≫ C言語Tips集 ≫ 配列・メモリ領域 ≫ 配列やメモリ領域の内容から任意の値を探索する

C言語Tips集 - 配列やメモリ領域の内容から任意の値を探索する

C言語で配列やメモリ領域の内容から任意の値を探索するには stdlib.h の bsearch 関数を使用します．

bsearch

#include <stdlib.h>

void *bsearch (
    const void *key,
    const void *base,
    size_t nmemb,
    size_t size,
    int (*compar)(const void *, const void *)
);

bsearch 関数は，base が指すオブジェクトの配列 (要素数が nmemb 個，各要素の大きさが size である配列) から，key が指すオブジェクトに一致する要素を探索する関数です．なお，base が指す配列は昇順に整列 (sort) されている必要があります．

bsearch 関数の引数をまとめると以下のようになります．

引数

  • key: 探索キー
  • base: 探索する配列
  • nmemb: 配列の要素数
  • size: 配列の個々の要素のサイズ
  • compar: 比較関数

比較関数

bsearch 関数を使用するには，事前にプログラマが比較関数 (compar) を実装しておく必要があります．比較関数は以下のルールに基づいて実装します．

  • 第 1 引数が第 2 引数より小さい場合: 0 より小さい値を返す
  • 第 1 引数が第 2 引数と一致する場合: 0 を返す
  • 第 1 引数が第 2 引数よりも大きい場合: 0 より大きい値を返す

比較関数は key へのポインタを第 1 引数とし，配列要素へのポインタを第 2 引数として呼び出されます．

C言語サンプルプログラム

以下に bsearch 関数を使用して int 型の配列を探索するサンプルプログラムを示します．

/* header files */
#include <stdio.h>
#include <stdlib.h>

/* functions */
int compar(const int *val1, const int *val2);

/* main */
int main(void) {
    int ary[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int key, *result;
    int n = sizeof(ary) / sizeof(ary[0]);

    /* keyを入力 */
    scanf("%d", &key);

    /* 探索 */
    result = bsearch(&key, ary, n, sizeof(int),
        (int (*)(const void *, const void *))compar
    );

    if ( result == NULL ) {
        fprintf(stderr, "%dは見つかりませんでした.\n", key);
    } else {
        printf("%dは配列の%d番目の要素です.\n", 
            key, (int)(result - &ary[0]));
    }

    return EXIT_SUCCESS;
}

/**
 * 比較関数
*/
int compar(const int *val1, const int *val2) {
    if ( *val1 < *val2 ) {
        return -1;
    } else if ( *val1 == * val2 ) {
        return 0;
    } else {
        return 1;
    }
}

実行例

サンプルプログラムの実行結果は以下のようになります．

( 1 を入力)
1は配列の0番目の要素です.

( 8 を入力)
8は配列の7番目の要素です.

( 0 を入力)
0は見つかりませんでした.

( 9 を入力)
9は見つかりませんでした.

Cプログラマの必読書

たくさんあるC言語関連の書籍の中でも特に役に立った本です．よかったら参考にしてみてください．

C実践プログラミング 第3版

C言語の実践的参考書．少々値段は張りますが初心者を脱しようとしている人は絶対に読むべきです．
文法だけでなく，コーディングスタイルやデバッグなど文字通り「実践的」なことが書かれているので非常にためになります． オライリーの本は，読みにくい本が多いのですが本書はとても読みやすくオススメです．


C言語ポインタ完全制覇 (標準プログラマーズライブラリ)

ポインタの解説書としては最高の書籍です．
この1冊でポインタを完全に理解することができます．全くの初学者が読むには敷居が高いですが，入門書を読み終えた後に読むと非常に有益です．

整列・探索