C言語 構造体のバイナリサーチ(二分探索) - stdlib.h - [ bsearch ]

2008.11.05 Wednesday | by LRESULT


イナリサーチ(二分探索)を行うには、bsearch()を使います。

今回は、応用編として構造体を対象としたバイナリサーチをやってみます。

バイナリサーチを行うには、まず検索対象の要素が、
  昇順でソートされている必要があります。

バイナリサーチの基本編は、こちら


bsearch
書式 void* bsearch( const void *key,
                     const void *base,
                     size_t n,
                     size_t size,
                     int (*comp)(const void *c1, const void *c2 ) )
機能 バイナリサーチ(二分探索)を行う
引数 const void *key : 検索する値
const void *base : 検索する配列
size_t n : 配列要素の個数
size_t size : 配列要素のサイズ
int (*comp)(const void *c1, const void *c2 ) ) : 比較関数
戻り値 検索が成功した場合は、要素のポインタを返し、
発見出来なかった場合は、NULLを返します。



比較関数(comp)の戻り値
c1 < c2 負の値
c1 == c2 0
c1 > c2 正の値

比較関数の戻り値には、上記の規則があります。





サンプルコード
時刻から生成した乱数を、構造体「TEST」のメンバ変数 a, b, c に代入し、
メンバbを昇順ソート後に、バイナリサーチでメンバbが「30」となる値を検索します。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct{
  int a;
  int b;
  int c;
}TEST;

int comp_sort( const void *c1, const void *c2 );
int comp_search( const void *c1, const void *c2 );

int main(void)
{
  int i, key=30;
  TEST *result;
  TEST base[10];

  /* 乱数の生成 */
  srand( (unsigned int)time( NULL ) );

  for( i=0; i<10; i++ ){
    base[i].a = rand() % 50;   /* 0〜49の乱数 */
    base[i].b = rand() % 50;
    base[i].c = rand() % 50;
    printf( "%d¥t", base[i].a );
    printf( "%d¥t", base[i].b );
    printf( "%d¥t", base[i].c );
    printf( "¥n" );
  }

  /* クイックソート */
  printf( "¥n--クイックソート実行--¥n¥n" );
  qsort( base, 10, sizeof(TEST), comp_sort );

  /* ソート後のデータを表示 */
  for( i=0; i<10; i++ ){
    printf( "%d¥t", base[i].a );
    printf( "%d¥t", base[i].b );
    printf( "%d¥t", base[i].c );
    printf( "¥n" );
  }

  /* バイナリサーチで30を検索 */
  printf( "¥n%d を検索¥n", key );
  result = (TEST *)bsearch( &key, base, 10, sizeof(TEST), comp_search );

  if( result == NULL ) printf( "%d は見つかりませんでした¥n", key );
  else printf( "%d が %d番目の要素として見つかりました¥n", key, result - base );

  return 0;
}

/* 比較関数 クイックソート用 */
int comp_sort( const void *c1, const void *c2 )
{
  TEST test1 = *(TEST *)c1;
  TEST test2 = *(TEST *)c2;

  int tmp1 = test1.b;
  int tmp2 = test2.b;

  return tmp1 - tmp2;
}

/* 比較関数 バイナリサーチ用 */
int comp_search( const void *c1, const void *c2 )
{
  TEST test2 = *(TEST *)c2;

  int tmp1 = *(int *)c1;  /* c1は bsearch()の第1引数(=key) */
  int tmp2 = test2.b;

  return tmp1 - tmp2;
}



結果
14      1       23
38      40      41
43      35      2
29      30      4
37      39      10
35      11      19
32      8       8
23      43      43
40      36      19
18      10      34

--クイックソート実行--

14      1       23
32      8       8
18      10      34
35      11      19
29      30      4
43      35      2
40      36      19
37      39      10
38      40      41
23      43      43

30 を検索
30 が 4番目の要素として見つかりました
と、TEST構造体のメンバb に「30」という値があれば、上記のように表示します。

バイナリサーチを行う際で注意する所は、
「比較関数( comp_search )の第1引数( c1 )には、
bsearch()の第1引数( key )が渡される」
という所です。
その為、comp_search()の引数c1 を int型でキャストしています。

これを間違えると、コンパイルは通るのに
検索は失敗していまうという、困った事態になります。

カテゴリ:C言語 stdlib.h | 22:14 | comments(0) | trackbacks(0) | -


コメントする











この記事のトラックバックURL

http://simd.jugem.jp/trackback/117

トラックバック