FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
line

バイナリサーチ

プログラム全文はこちら


バイナリサーチとは探索アルゴリズムの一つですね
基本的な探索アルゴリズムは[0]~[50]とかまでの配列を順に見ていき値があればありました的なflgを立てれば終了です
10や20程度の要素数を持った配列ならそれでもかまいませんがもし配列が1000や2000あったら・・・
順に見ていくのはちょっと処理的に良くないです、ということで登場したのがバイナリサーチ・・・だと思いますw
とりあえず成り行きとかはwikiとかが詳しいかと・・・


ちなみにこのアルゴリズム、実は使用条件があります、それは配列の中身が降順か昇順になっていることです
(昇順 -> 小さいものから大きいものへ順)
(降順 -> 大きいものから小さいものへ順)


この流れを簡単にまとめます(自分なりに)
int left=0; //< 配列場所(左)
int right=6; //< 配列場所(右)
int center; //< 配列場所(中央)

配列
[0][1][2][3][4][5][6]
(今回は見つけたい値が[6]に入っているとします)
(値は昇順に入っているとします)



while文を実行します、条件は(left <= rigth)

最初にcenterを設定 -> center=(int)((right+left) / 2);

この時点での変数の中身は以下の通り
left=0
right=6
center=3

[0][1][2][3][4][5][6]


centerを見て見つけたい値があればwhile文を抜けますが今回は[6]に値が入っているとしますので今回は[3]を見ているので検索続行


続行する場合、centerの値とleft、rightをそれぞれ比べます
昇順なので[6]に入っている値はcenterより大きいです
ということでcenterより小さい値であるleft方面の数(つまり[0]~[3])までは切り捨てます

leftを再設定 -> left=center+1;
(leftの配列を指す位置は[4]になりました)

ここまできたら一旦処理は終了です、while文の最初に戻ります
再びcenterの設定です

この時点での変数の中身は以下の通り(二回目)
left=4
right=6
center=5

[4][5][6]

はい見つからない。ということでleft再設定 & center再設定

この時点での変数の中身は以下の通り(三回目)
left=6
right=6
center=6

[6]


はい見つかりましたね、3回目で発見です


ここで見つからなければleftが再設定され7となります
そうなるとwhile文の条件である(left <= right)を満たなくなるのでwhile文を抜けることになります


サンプルではflgを用意して見つかった時にtrueにするという方法をとっています


ちなみに今回は昇順であることを前提にして考えましたが、降順の場合はcenterの指す配列の中身が
大きければleft=center+1;
小さければright=center-1;と逆にしてあげれば解決します

まぁ答えを書くと
index[center] < ANS -> index[center] > ANS
index[center] > ANS -> index[center] < ANS
と変更するか
if文の中身を逆にすればいいだけです。少し順を追って見れば理解できるのではないかなと思います。
少し複雑なアルゴリズムですがすごく使えるものです


ただし何度も言いますが配列の中身が昇順か降順であることが絶対です
そうでなければこのアルゴリズムは使用できませんのでご注意を・・・

スポンサーサイト
line
line

comment

管理者にだけ表示を許可する

line
line

FC2Ad

line
プロフィール

否健康食品オワタ

Author:否健康食品オワタ
27.142.178.77 (1)
27.142.178.77 (2)

2714217877.gif

line
最新記事
line
最新コメント
line
最新トラックバック
line
月別アーカイブ
line
カテゴリ
line
検索フォーム
line
RSSリンクの表示
line
リンク
line
ブロとも申請フォーム

この人とブロともになる

line
QRコード
QR
line
sub_line
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。