C言語入門講座。関数、サンプル集を参考にして、 C言語をマスターしよう。初心者から上級者まで。

配列要素を検索する(バイナリサーチ)

2012.08.10

bsearch関数は、配列中から該当する要素を検索します。配列の内容は昇順にソートされていなければなりません。

#include <stdlib.h>
void bsearch(const void *key, void *base, size_t nmemb, size_t size,
          int(*compar)(const void *, const void *));

*keyは検索キーを指定します。
*baseは検索対象の配列を指定します。
nmembは配列の要素数を指定します。
sizeは配列要素の大きさをバイト単位で指定します。
*comparは検索キーの大小関係をbsearch関数に知らせる関数を指定します。

戻り値として、検索が成功した場合は、当該要素へのポインタが、失敗した場合は、NULLが返ります。該当する要素が複数あった場合は、どの要素が返されるかは不定です。

第5引数に指定する関数はbsearch関数から呼び出され、仮引数として比較対象の2つの要素が渡ってきます。要素中の検索キーの大小関係をチェックして戻り値として、次の値を返します。(第1引数は*keyです。)

  1. 第1引数が第2引数に対して小さい場合は、0より小さい値を返します。
  2. 第1引数と第2引数が等しい場合は、0を返します。
  3. 第1引数が第2引数に対して大きい場合は、0より大きい値を返します。

次の例題プログラムは、ファイルの内容を構造体配列に読み込んで、番号を検索キーにして検索しています。なお、ファイルの内容は番号をキーとして、昇順にソートしてあります。

プログラム 例

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

/* メンバーの個人情報 */
struct member {
  int      number;         /* 番号 */
  char     name[20];       /* 名前 */
  double   height;         /* 身長 */
  double   weight;         /* 体重 */
  double   jump;           /* 最高到達点 */
};
/* bsearch関数の検索キー比較関数 */
int SearchComp(const void *, const void *);

int main()
{
  FILE             *fp;
  struct member    member_list[20];
  struct member    key;                /* 検索キー */
  struct member    *res;                /* 検索結果 */
  int              list_cnt;

  if ((fp = fopen('beijing_2008.csv', 'r')) == NULL) {
    fprintf(stderr, 'ファイルのオープンに失敗しました\n');
    abort();
  }

  list_cnt = 0;
  /* メンバー情報入力 */
  while(fscanf(fp, '%d,%[A-Za-z],%lf,%lf,%lf',
      &member_list[list_cnt].number, member_list[list_cnt].name,
      &member_list[list_cnt].height, &member_list[list_cnt].weight,
      &member_list[list_cnt].jump) != EOF) {
    ++list_cnt;
  }
  fclose(fp);

  while (1) {
    printf('検索する選手の番号を入力してください ==> ');
    scanf('%d', &key.number);

    if (key.number != 0) {
      /* member_listを番号をキーにして検索 */
      res = bsearch(&key, member_list, list_cnt,
                   sizeof(struct member), SearchComp);

      if (res != NULL) {
        printf('番号 名前                   身長   体重  最高到達点\n');
        /* 検索結果を出力 */
        printf('%3d  %-20s %6.1f %6.1f %6.1f\n',
          res->number, res->name, res->height, res->weight, res->jump);
      }
      else {
        printf('検索できませんでした\n');
      }
    }
    else {
      break;
    }
  }

  return 0;
}

/* bsearch関数の検索キー比較関数 */
int SearchComp(const void *p1, const void *p2)
{
  struct member *cmp1 = (struct member *)p1;
  struct member *cmp2 = (struct member *)p2;

  return (cmp1->number - cmp2->number);
}

例の実行結果

$ cat beijing_2008.csv
1,kurihara,186,69,305
2,tajimi,180,70,309
3,takesita,159,52,280
4,oomura,184,70,319
5,takahasi,170,65,290
6,sano,159,54,260
7,sugiyama,184,66,310
8,sakurai,167,63,290
9,kanou,174,65,298
11,araki,186,79,307
12,kimura,184,66,298
14,kawai,168,63,280
$
$ ./bsearch.exe
検索する選手の番号を入力してください ==> 1
番号 名前                   身長   体重  最高到達点
  1  kurihara              186.0   69.0  305.0
検索する選手の番号を入力してください ==> 14
番号 名前                   身長   体重  最高到達点
 14  kawai                 168.0   63.0  280.0
検索する選手の番号を入力してください ==> 10
検索できませんでした
検索する選手の番号を入力してください ==> 7
番号 名前                   身長   体重  最高到達点
  7  sugiyama              184.0   66.0  310.0
検索する選手の番号を入力してください ==> 15
検索できませんでした
検索する選手の番号を入力してください ==> 0
$

関連記事