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 | 正の値 |
※ 比較関数の戻り値には、上記の規則があります。
時刻から生成した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番目という意味です。 また、何度も出ていますが、 昇順に並べ替えてからでないとバイナリサーチは出来ません。 同じ値がある場合は、どちらがヒットするかは不定です。 |