*二分探索 [#l49ba146]

このページは競技プログラミングに興味のある方向けに二分探索を簡単に説明するページです

**二分探索って何？ [#s601c470]

探索アルゴリズムの一種で"ソートされたデータ"から目的の値を持つ要素を探すアルゴリズムです

**線形探索と何が違うの [#a139d21d]
線形探索では'''O'''(N) ＝ N でしたが、二分探索では'''O'''(N) ＝ log(2,N)で終了します

**ならいつも二分探索を使えばいいんじゃない？ [#q36a8a9f]
二分探索を線形探索と比較した際に生じるデメリットは主に以下の2点です~
1.実装が面倒~
2.ソートをしておく必要がある(ソートされたデータにしか適用できない)~

とくに2が重要で、この前提が満たされていないデータに対しては線形探索で泥臭くいくしかありません~

**ソートしてから二分探索すればいいんじゃない？ [#mb6cf5f5]
クイックソートの時点で'''O'''(N) ＝ N・log(N)の計算量がかかるので線形探索したほうがいいです~

**どうやるんですか [#a6e57759]
配列に数値が格納されており、昇順にソートされているとします。目的の値は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に戻る~

要するに「目的の値が存在している可能性のある区間の中央値を調べる」ということを繰り返すわけですね~

**再帰関数で実装したぞ [#id593e02]
別にいいですけどループ文1つで出来るんで、無駄に高級なことはする必要は無いですよ~
競技プロコンでは時間が限られていますから、「自分が確実に書くことのできるコードを書く」「わかりきった処理で無駄な時間を使わない」ということが大事です~
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS