二分探索 - bbr-program-memo

二分探索

Binary search

バイナリサーチ

ソート済みの配列に対して、中点の値と比較して大小により、半分のどちら側か判定を繰り返して値を探索する方法。

計算量は$ \Omicron(\log_2 n)

中点$ 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

// 擬似コードなのでこのままでは動かない。

/// めぐる式二分探索

/// * 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;

}