二分探索について本気出して考えてみた

ちょっと二分探索について分からないことがあったのでメモっておこうと思います。

二分探索は探索空間を半分にしていくことでnの大きさの空間をO(logn)で探索出来る代表的なアルゴリズムです。地球上の人類70億人から1人を見つけるのも33回で出来ます（ちょっと違うか）。

例えば、単調性のあるcheck関数（あるs1でcheck(s1) = trueならばcheck(t1) = true (s1 <= t1) かつ あるs2でcheck(s2) = falseならばcheck(t2) = false (t2 <= s2)）において、check(l) = trueになる最小のlを求めたい場合は以下のコードで出来ますね。

long u = MAX; //MAXは探索空間の最大値
long l = MIN; //MINは探索空間の最小値
if(check(u) == false){return;} //最大値でfalseだったら全部false
		
while(l < u){
	long m = (l + u) / 2;
	if(check(m)) u = m; //mはまだ探索空間に残しておく
	else l = m + 1; //mは探索空間外
}
return l;

check(p) = true、check(p - 1) = falseを満たすpを線形探索だとO(MAX - MIN)かかりますが、これだとO(log(MAX - MIN))でできます。

ただ、上のコードを眺めていて少しよく分からなかったことが合ったのでいろいろ考えてみました。

( 1 )絶対に無限ループは起こらない？

　(i)最後の代入がu = mの場合
　u = m = (l + u) / 2
　l = t, u = t + rとおきます。ここで、whileの条件よりl < uなので、1 <= rが成り立ちます。
　m = (2 * t + r) / 2 = t + [r / 2] （[]はガウス記号）
　よってu ≠ mが成り立つので無限ループしません。

　(ii)最後の代入がl = m + 1の場合
　これはl = mによる無限ループは起こりません。 +1がかかっているためです。m = l - 1になりつづけるとまずいですが、m = (l + u) / 2、l < uよりl <= mです。

　以上より、無限ループは起こりません。

( 2 )whileの条件式は l <= u でなくていいのか？
　l < uで本当に空間内全てが評価出来るのでしょうか？大丈夫なのか考えてみました。

　(i) uからlに近づく場合は最終的にlが求める最小値であることが評価出来ればOKです。u = l + 1の時、u = [(l + l + 1) / 2] = lになるのでOKです。intの除算の小数切り捨てが上手く効いています。

　(ii)lからuに近づく場合は最終的にuが求める最小値であることとu - 1が求める最小値であることが評価出来ればOKです。
　　u - 1が最小の時を考えます。l = u - 2の時はm = u - 1 ( <= u - 1)になり、check(m)が評価されるので(i)に帰着できます。uが最小の時もこの手順を通るので(i)に帰着できます。

次に、逆に最大値を求める二分探索を考えます。
今度のcheck2関数は「あるs1でcheck2(s1) = trueならばcheck2(t1) = true (t1 <= s1) かつ あるs2でcheck2(s2) = falseならばcheck2(t2) = false (s2 <= t2)」を満たします。
さきほどのコードをコピペしてちょっと変えて作ります。

long u = MAX; //MAXは探索空間の最大値
long l = MIN; //MINは探索空間の最小値
if(check2(l) == false){return;} //最小値でfalseだったら全部false
		
while(l < u){
	long m = (long)Math.ceil((l + u) / 2); //切り捨てではなく切り上げ
	if(check2(m) == false) u = m - 1; //mは探索空間外
	else l = m; //mはまだ探索空間に残しておく
}
return m;

最大値を求める場合はm = (l + u) / 2では駄目です。最小値の時の（1）の(i)と（2）の(i)を見ると理由が分かります。切り捨てではなく切り上げにしなければなりません（関係ないけど、なんでJavaのMath.ceil関数はdoubleなんだろう。longにすればいいのに・・・）。

疑問に思ってネットで調べてみたんですが、なかなか見つからなかったので考えてみました。もしかしたらなんか間違ってるかもしれませんが・・・（実験とかしてません。机上の空論です）。

（追記 : 2013/03/08）

切り上げは

long m = (long)Math.ceil((l + u) / 2);

ではなく

long m = (l + u) / 2 + (l + u) % 2;

のようにキャストしない方がいいですね。