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 正の値

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





サンプルコード
時刻から生成した20個の乱数を、まず昇順にソートし、
バイナリサーチで「30」という値を検索し、結果と配列の要素番号を表示します。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int comp( const void *c1, const void *c2 );

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

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

  for( i=0; i<20; i++ ){
    if( i % 4 == 0 ) printf( "¥n" );
    base[i] = rand() % 100;   /* 0〜99の乱数 */
    printf( "%d¥t", base[i] );
  }

  /* クイックソート */
  printf( "¥n¥n--クイックソート実行--¥n" );
  qsort( base, 20, sizeof(int), comp );

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

  /* バイナリサーチで「30」を検索 */
  printf( "¥n%d を検索¥n", key );
  result = (int *)bsearch( &key, base, 20, sizeof(int), comp );

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

  return 0;
}

/* 比較関数 */
int comp( const void *c1, const void *c2 )
{
  int tmp1 = *(int *)c1;
  int tmp2 = *(int *)c2;

  if( tmp1 < tmp2 )  return -1;
  if( tmp1 == tmp2 ) return  0;
  if( tmp1 > tmp2 )  return  1;
}



結果
51      39      52      60
29      65      95      73
55      71      71      58
96      88      3       82
30      43      95      22

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

3       22      29      30
39      43      51      52
55      58      60      65
71      71      73      82
88      95      95      96
30 を検索
30 が 3番目の要素として見つかりました
検索対象の「30」が見つかった場合には、このように表示されます。
配列要素の番号を求めるには、
結果の result から配列の先頭アドレス base を引いて求めています。

要素番号は、0から数えて3番目という意味です。

また、何度も出ていますが、
昇順に並べ替えてからでないとバイナリサーチは出来ません。
同じ値がある場合は、どちらがヒットするかは不定です。

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


コメントする











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

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

トラックバック