二分探索

二分探索 †

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

二分探索って何？ †

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

線形探索と何が違うの †

配列の要素数をNとすると線形探索ではO(N) でしたが、二分探索ではO(log2(N))で終了します

ならいつも二分探索を使えばいいんじゃない？ †

配列の要素探索における二分探索を線形探索と比較した際に生じるデメリットは主に以下の2点です
1.実装が面倒
2.ソートをしておく必要がある(ソートされたデータにしか適用できない)

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

ソートしてから二分探索すればいいんじゃない？ †

クイックソートの時点でO(NlogN)の計算量がかかるので基本的には線形探索したほうがいいです

しかし、「ある値を探す」という処理（クエリ）がC個ある場合は、
ソートが、O(NlogN)、探索がO(ClogN)となります。
ソートしない場合、探索がO(CN)となるので、N≦100000、C≦100000などの制約ではソートしたほうがよいでしょう。

どうやるんですか †

配列に数値が格納されており、昇順にソートされているとします。目的の値は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つで出来るんで、無駄に高級なことはする必要は無いですよ
競技プロコンでは時間が限られていますから、「自分が確実に書くことのできるコードを書く」「わかりきった処理で無駄な時間を使わない」ということが大事です

応用！ †

二分探索は、ソートされた配列から値を検索するだけにしか使えないわけではありません。
二分探索の定義を以下のように考えてみましょう。

(狭義)単調増加(or 減少)関数f(x)について、「f(x)f(x+ε)≦0」（ただし、εは十分に小さい）となるxを求めるアルゴリズム

このように二分探索を定義してあげると、f(x)を問題によってうまく決めてあげることで、二分探索を適用することができるようになります。
この場合の「狭義」とは、どのような定義域内のxについても、「f(x) = f(x +ε)」となることがないということです。
要するに、同じ値でとどまっているということは無いということですね。
この条件がなくても一応二分探索できますが、求まるxは、f(x)≒0をみたすxのうちどれかになってしまいます。

f(x)f(x+ε)≦0とは、要するにxを堺にしてf(x)の符号が逆転するということです。異符号の実数の掛け算は負になりますよね。

実例見せて †

ソート済み配列から値を探す †

ソート済み配列をarray、探索する値をsearchとして、

f(x) = array[x] - search

とすれば、条件を満たす。

チキンレース †

与えるエネルギーE(>0)に対して、飛距離rをr=2Eとする。許される最大の飛距離がtargetのとき、エネルギーを最大いくらまで与えることができるか。

f(E) = 2 * E - target

とすることで、条件を満たす。
(※このくらいなら数式で一発で求めたほうが早いです。（E = target / 2）
しかし、飛距離rが複雑、だけれども単調増加な関数（例えばr=E^4+2E^3+E^2、物理的にはありえないけど）
で与えられたら解の公式を考えるのが難しくなります。こんな時のための二分探索です。)

課金ゲー †

N円課金したとき、N≧minNであれば目的のモノ、そうでない時は違うモノが渡される。
できるだけ少ない金額で目的のモノを得たい。minNを求めよ（最低何円必要か）。
（もちろん、minNは直接は分からないが、N円課金した時の「結果」は何度も聞くことができる）

f(x) = -1 (x円課金して違うモノが渡される時)
f(x) = 1 (x円課金して目的のモノが渡される時)

とすることで、条件を満たす。
1円から順番に試してみる方法はO(N)かかるが、こちらはO(logN)となっている。