計算半ばには

Question

私は、バイナリサーチのための以下のアルゴリズムを持っていたアルゴリズムの本を読んでいた。

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;である」と言いますm = l + (u-l)/2によって。

どのようにオーバーフローが発生するのかわかりません。私がアルゴリズムをいくつかの異なる入力のために動かすと、配列のインデックスから中間値が外れることはありません。

どのような場合にオーバーフローが発生しますか？

Answer 1

このpostは、この有名なバグを詳細にカバーしています。他の人が言ったように、それはオーバーフローの問題です。次のようにリンクをお勧め修正は次のとおりです。

int mid = low + ((high - low)/2); 

// Alternatively 
int mid = (low + high) >>> 1; 

場合には負のインデックスが許可されていることを、おそらくも言及する価値がある、または多分それはで値を検索、例えば（検索されていても、配列ではありませんいくつかの条件を満たす整数の範囲）、上のコードは正しくないかもしれません。この場合、醜いものとして、

(low < 0 && high > 0) ? (low + high)/2 : low + (high - low)/2 

が必要な場合があります。 1つの良い例は、Integer.MIN_VALUE-の範囲全体に対して単純にバイナリ検索を実行することによってsearching for the median in an unsorted array without modifying it or using additional spaceです。

Answer 2

潜在的なオーバーフローは、追加自体のl+uです。

これは実際にはJDKのバイナリ検索のa bug in early versionsでした。

Answer 3

(l+u)が最初に評価され、intがオーバーフローする可能性があるため、(l+u)/2は間違った値を返します。

Answer 4

ジェフがこのバグについて読むには本当に良いと提案しました。post、ここでは概要を要約しています。

Programming Pearls Bentleyは、類似の行が "mをlとuの平均に設定し、最も近い整数に切り捨てられる"と述べています。それに直面して、このアサーションは正しく表示されるかもしれませんが、int変数の大きな値が低いと高い場合に失敗します。具体的には、ローとハイの合計が最大正のint値（2^31 - 1）より大きい場合は失敗します。合計は負の値にオーバーフローし、2で割った値は負のままです。 Cでは、予測できない結果を伴う配列のインデックスが範囲外になります。 Javaでは、ArrayIndexOutOfBoundsExceptionをスローします。