二分探索のアルゴリズム
代表的な探索のアルゴリズムです。
これを使う条件として、探索したい要素を含んだ列がソートしてある必要があります。
二分探索の動きを見ていきましょう。
二分探索は探索範囲の真ん中の値と探索する値を比較し、その大小で探索範囲を絞り込んでいきます。
例を見てみましょう。
以下の配列i[]から3を探します。
i[0] | i[1] | i[2] | i[3] | i[4] | i[5] | i[6] | i[7] | i[8] | i[9] |
---|---|---|---|---|---|---|---|---|---|
0 | 3 | 5 | 7 | 8 | 10 | 11 | 15 | 21 | 22 |
まず真ん中の値(偶数個ならどちらか)であるi[5]と探索値3を比較します。
3はi[5]よりも小さいのでi[5]以降にはありません。
よって探索範囲をi[0]からi[4]に変更します。
同様に3とi[2]を比較するとi[2]の方が大きいので探索範囲をi[0]からi[1]にします。
最後にi[3]と3を比較するとこれは一致します。
以上が二分探索のアルゴリズムです。
ソースコード
以下が二分探索のソースコードの例です。
binary_search_sample1.c
#includeint main(void) { int a[] = { 0,1,2,3,4,5,6,7,8,9 }; int serch = 3; int right = 0, left = 9; while (right < left) { printf("a"); int mid = (left + right) / 2; if (serch == a[mid]) { printf("%dは%d番目", serch, mid); break; } else if (serch > a[mid]) right = mid; else if (serch < a[mid]) left = mid; } return 0; }