多くの二分探索の実装に潜む落とし穴――整数オーバーフロー問題とは

二分探索（バイナリサーチ）は線形探索よりも優れたアルゴリズムであり、O(log n) の時間で実行できることで知られています。しかし、世の中に出回っている実装の多くには、実は共通の欠陥が潜んでいます。次のような二分探索関数のコードを見てみましょう。

問題のあるコード例

int binarySearch(int array[], int start, int end, int key){
    if(start <= end){
        int mid = (start + end) / 2; // リストの中間位置
        if(array[mid] == key)
            return mid;
        if(array[mid] > key)
            return binarySearch(array, start, mid-1, key);
        return binarySearch(array, mid+1, end, key);
    }
    return -1;
}

このコードは、start と end が小さいうちは正常に動作します。ところが、(start + end) の合計が 2³² − 1 を超えるほど大きな値になると、整数のラップアラウンド（オーバーフロー）によって負の値が返されてしまうことがあります。負の数は配列のインデックスとして使用できないため、メモリへの不正アクセスやプログラムの誤動作といった深刻な問題につながるのです。

この問題を回避するための方法はいくつかあります。

方法1：減算ベースの計算（推奨・汎用）

int mid = start + ((end - start) / 2)

加算ではなく減算を使うことで、オーバーフローを確実に防げます。C、C++、Java など、どの言語でも利用できる最も一般的で安全な手法です。

方法2：>>> 演算子を使用する（Java のみ）

int mid = (start + end) >>> 1

Java には符号ビットを考慮せずに右シフトを行う >>> 演算子が用意されています。これを使えば、加算結果がオーバーフローしても正しい中間値が得られます。ただし、C や C++ には >>> 演算子が存在しないため、この方法は Java 専用です。

方法3：unsigned 型へキャストする（C/C++ 向け）

int mid = ((unsigned int) low + (unsigned int) high) >> 1

C や C++ で >>> が使えない場合の代替策です。値を unsigned int にキャストしてからシフトすることで、符号なし整数同士の加算となり、たとえラップアラウンドしても動作が言語仕様上定義されているため、正しい中間値を求められます。

まとめ

一見完璧に見える二分探索のコードにも、このような整数オーバーフローという罠が隠れていることがあります。特に大規模な配列を扱うシステムでは、中間値の計算方法を見直し、「start + ((end - start) / 2)」のような安全な書き方を採用することをおすすめします。有名な事例として、過去には JDK の標準ライブラリでも同様のバグが発見され話題になりました。単純なアルゴリズムこそ、細部まで注意深く実装することが重要です。