java - この二分探索の何が問題になっていますか?

Question

public static int binsrch (int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (true) { 
        if (low > high) return -(low+1); 
        int mid = (low + high)/2; 
        if      (a[mid] < key)  low = mid + 1;
        else if (a[mid] > key) high = mid - 1;
        else    return mid;
}

誰でも助けることができますか？

Answer 1

少なくとも 2 つ、場合によっては 3 つの問題があると思います。

を使用しています(low + high)/2。配列が非常に大きい場合、加算は負の数にオーバーフローする可能性があります。その場合、2 で割ると負のインデックスになります。これは、を使用して修正できます(low + high)>>>1。

文書化されていません。配列内にキーが見つかった場合は一致インデックスを返し、ミスした場合は負の値を返すことを意図していると推測しています。ドキュメントがないため、否定的な結果が何を表しているのか正確にはわかりません。

不足している仕様によっては、追加の問題が発生する可能性があります。