0 
l = -1; u = n;
while l+1 != u
    m = l + (u-l)/2;
    if x[m] < t
        l = m;
    else
        u = m;
p = u;
if p >= n || x[p] != t
     p = -1;

上記のコードでは、x[-1]<tおよびx[n]>=tおよびn>=0と想定しています。上記のコードは、ランダムなものを返す代わりに、整数配列x[0..n-1]内の整数tの最初の出現を返すことができる修正された二分探索です。

私の質問はこのようなものです：

上記のコードが常に停止するのはなぜですか？誰かがそれを説明したり証明したりできますか？

ありがとう、

4

1 に答える 1

4

反復ごとに、整数演算の制約内でlとの間のギャップが半分になるためです。u(正の) 整数の 2 分の 1 のすべてのシーケンスは、最終的に 1 に到達する必要があります。これが終了条件です。

于 2012-07-04T23:09:54.903 に答える