![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
このページは競技プログラミングに興味のある方向けに二分探索を簡単に説明するページです
探索アルゴリズムの一種で"ソートされたデータ"から目的の値を持つ要素を探すアルゴリズムです
線形探索ではO(N) ＝ N でしたが、二分探索ではO(N) ＝ log(2,N)で終了します
二分探索を線形探索と比較した際に生じるデメリットは主に以下の2点です
1.実装が面倒
2.ソートをしておく必要がある(ソートされたデータにしか適用できない)
とくに2が重要で、この前提が満たされていないデータに対しては線形探索で泥臭くいくしかありません
クイックソートの時点でO(N) ＝ N・log(N)の計算量がかかるので線形探索したほうがいいです
配列に数値が格納されており、昇順にソートされているとします。目的の値はTとします
1.位置を示すピポットを2つ(A, B)用意し、左端の要素(最小値)の位置をAに、右端の要素(最大値)の位置をBに充てる
2.(A+B)/2に相当する要素のデータをチェックし、目的の値Tとチェックします。参照値RがTに等しければ探索を終了します
3.R>TならピポットBを参照しているデータ位置に変更します(つまり、B=(A+B)/2とする)。
同様にR<TならピポットAを参照しているデータ位置に変更します
4.2に戻る
要するに「目的の値が存在している可能性のある区間の中央値を調べる」ということを繰り返すわけですね
別にいいですけどループ文1つで出来るんで、無駄に高級なことはする必要は無いですよ
競技プロコンでは時間が限られていますから、「自分が確実に書くことのできるコードを書く」「わかりきった処理で無駄な時間を使わない」ということが大事です
