C言語 構造体のバイナリサーチ(二分探索) - stdlib.h - [ bsearch ]
2008.11.05 Wednesday | by LRESULT
バイナリサーチ(二分探索)を行うには、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を返します。 |
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型でキャストしています。 これを間違えると、コンパイルは通るのに 検索は失敗していまうという、困った事態になります。 |