12

二分探索は、再帰的、反復的、条件付きなど、さまざまな方法で実装できます。Bentley の本「Programming pearls : Writing correct programs」から引用しました。これは反復実装であり、バグが含まれています。

 public class BinSearch 
    {
       static int search( int [] A, int K ) {
          int l = 0;
          int u = A. length -1;
          int m;
          while ( l <= u ) {
              m = (l+u) /2;
              if (A[m] < K){
              l = m + 1;
              } else if (A[m] == K){
                    return m;
              } else {
                    u = m-1;
              }
         }
    return -1;
    }
}

行 m = (l+u) /2; にバグが見つかりました。オーバーフローにつながる可能性があります。このバイナリ検索でこのオーバーフローを回避するにはどうすればよいでしょうか?

4

7 に答える 7

14

次のことを試してください。

変化する

m = (l+u) /2

に

m = (u-l) / 2 + l

(l+u) / 22^31 - 1 要素 (符号付き 32 ビット整数が保持できる最大値) の非常に大きな配列を考慮すると、缶がオーバーフローする理由が明らかになります。この場合、最初の反復は2^31 - 1 + 0大したことではないので問題ありませんが、l = m + 1ここの場合を考えてみましょう。2 番目の反復では、u は同じままで、l も同じである2^31 / 2ためl + u、オーバーフローが発生します。

u + lこのようにして、最初に l と u の間の相対的な中間を決定し、(u - l) / 2次に小さい数 l をそれに追加して絶対値にすることで、 の追加を回避しています。したがって、操作中m = (u-l) / 2 + l;に u の値を超えることはありません。

完全なコードを要約するには:

public class BinSearch 
{
    static int search( int [] A, int K ) 
    {
        int l = 0;
        int u = A. length -1;
        int m;

        while ( l <= u ) 
        {
            m = (u-l) / 2 + l;

            if (A[m] < K)
                l = m + 1;
            else if (A[m] == K)
                return m;
            else
                u = m - 1;
        }
        return -1;
     }
}
于 2013-07-07T06:49:07.060 に答える
2

変更してみる

m = (l+u) / 2

に

m = l + (u - l) / 2

両方が等しいことと、2 番目のステートメントがオーバーフローを防止していることは簡単にわかります。

于 2013-07-07T07:43:02.683 に答える
1

反復実装の二分探索には確かにバグがあります。変更m = (l+u)/2。他の人が言及したように、整数オーバーフローにつながる可能性があります。それを に置き換えm = l + (u-l)/2ます。

経験上、バグのある二分探索の実装を何度も見てきました。二分探索ですが、分割統治を含む単純な概念を正しく理解するのは難しい場合があります。上記のm割り当てを変更するのは簡単です。お役に立てれば...

于 2013-07-12T15:48:02.350 に答える