二分探索
Binary search
バイナリサーチ
分割統治の考え方で、領域を半分に区切りながら判定をしていく。 計算量は$ \Omicron(\log_2 n)になる。
基本的に3つの使われ方をする。(多くの場合、これらを区別せずに書いてあるので混乱しやすい。)
値検索
ソート済みの値の位置を検索する。(見つからなければ、値を挿入すべき位置を返す。)
大小判定による検索
compare(idx)
ある場所で大きいなら、そこよりは小さい範囲にある。
ある場所で小さいなら、そこよりは大きい範囲にある。
境界検索
ある判定式が成立する境界(最大または最小)の値を見つける。
指定した値に対する真偽判定による検索
is_ok(idx)
ある値で真なら真の範囲をそこまで広げる。偽なら偽の範囲をそこまで広げる。未知の範囲がなくなるまで繰り返す。
特定の要素が含まれる場所の検索
ある1つの要素が含まれる場所を見つける。
例えばプログラムソースで、バグが含まれる行を半分ずつコメントアウトして見つけるみたいな方法
近似値を見つけるようなケース
指定した範囲に対する真偽判定による検索
is_target_in_range(from, to)
半分に区切った範囲で見つからないなら、目的物はもう片方の範囲に含まれる。
ある程度の範囲に収まった時点で終了するのがセオリー (浮動小数点で範囲を絞るようなケース)
よくある「数あてゲーム」の例は大小判定なので値検索に近いが、配列を使っているわけではない。
値検索の基本的な考え方
(初期の終端位置は配列がa[0] ... a[n-1](n個)の時に、n となるべきか、n-1 となるべきか?)
ここでは終端位置をnとする。
配列を a とする。検索する値を x とする。
先頭位置sを0、終端位置eをnとする。
以下、e < s になるまで繰り返し
中点 m を求める。m = s + floor((e - s) / 2)
a[m] < x なら、e ← m とする。
a[m] > x なら、s ← m + 1 とする。
a[m] = x なら、mを発見場所として返して終了。
見つからなかった場合は s を挿入場所として返す。
発見場所と混同されないようにうまいこと何とかする。-(s+1)とするのが一般的か。
境界検索の基本的な考え方
判定式を f(x) とする。
ok位置とng位置を指定する。ok位置は必ず判定式が真となる位置、ng位置は必ず判定式が偽となる位置とする。
以下、ok位置とng位置の差が1より大きい間繰り返し (これにより中点が必ずok位置とは異なる場所になることが保証される。)
中点 m を求める。(m = floor((ok + ng) / 2))
f(m) = true なら、ok ← m とする。
f(m) = false なら、ng ← m とする。
ok位置を返す。
領域を半分に区切るとき
中点$ cは始点$ sと終点$ eとしたとき $ c = (s + e) / 2とすれば見つかるが、
実装上の細かなテクニックとして、$ c = s + (e - s)/2とすると、オーバーフローをある程度防ぐことができる。
長さが十分に小さくなったら線形探索に切り換えたが効率はよいかもしれない。
始点と終点の区間で取り扱うのが簡単。
始点と終点の間がなくなった時点で終了にする事ができる。
普通は離散(=整数)で、半開区間 [ok, ng), (ng, ok]にするのが簡単。
終了条件を満たさないなら ok と ng の間は2以上になるので2で割ると必ず1以上になる。
これは二分探索実装のハマりポイントで整数値の1は2で割ると0になるので、中間値と終了条件のミスでよく無限ループになってしまう。
ok と ng の間が1ということは、それが境界である事を示す。
ok と ng の間が0になる事はないのか?
ok が含まれていると仮定されているが、全部 ng のケースだと0になることがある。(要注意)
解の正否を使って、中点をそのまま始点、終点に代入する事ができる。
code:binary_search.rs
// Rust だが、擬似コードなのでこのままでは動かない。
/// めぐる式二分探索
/// * ok - 少なくともokとなる値
/// * ng - 少なくともngとなる値
/// * @return okとなる境界値
fn binary_search_meguru<T>(ok: T, ng: T, solve: &dyn Fn(T) -> bool ) -> T
{
let mut s = ok;
let mut e = ng;
while (if e >= s { e - s } else { s - e }) > 1 // absを自力実装
{
let mid = (s + e) / 2;
if solve(mid)
{
s = mid;
}
else
{
e = mid;
}
}
s
}
キーを検索する(そのものの位置を検索する)のとキーを挿入すべき位置を検索するというのとで微妙に異なる。
関連
Keyword: 2分探索