-2

私はこのコードを二分探索に持っています。

public class BinarySearch {

private static int location;
private static int a = 14;
static int[] numbers = new int[]{3, 6, 7, 11, 14, 16, 20, 45, 68, 79};

public static int B_Search(int[] sortedArray, int key) {
    int lowB = 0;
    int upB = sortedArray.length;
    int mid;
    while (lowB < upB) {
        mid = (lowB + upB) / 2;

        if (key < sortedArray[mid]) {
            upB = mid - 1;
        } else if (key > sortedArray[mid]) {
            lowB = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

public static void main(String[] args) {
    BinarySearch bs = new BinarySearch();
   location= bs.B_Search(numbers, a);
   if(location != -1){
       System.out.println("Find , at index of: "+ location);
   }
   else{
       System.out.println("Not found!");
   }
}
}

//出力：a = 14

見つかりません！！

なんで？

4

3 に答える 3

5

まず、デバッガーのコードをステップ実行して、何が問題なのかを理解できるかどうかを確認する価値があります。ただし、この特定のバグは診断が難しい場合があることを経験から知っています。

上限と下限が包括的であるか排他的であるかを理解する必要があります。上限は排他的だと思いますが、下限は包括的です（これはかなり正常です）。つまり、これは次のことを意味します。

upB = mid - 1;

実際には次のようになります。

upB = mid;

正しいインデックスがそうではないことはわかっていますがmid、それよりも低い可能性があります。現在のコードはその値を除外しています...一方、固定コードは。のみを除外していmidます。

他の回答が示しているように、代わりに別の方法で初期化して比較し、それを包括的上限にすることができます。個人的には、コンピュータサイエンスの多くがそのように機能するため、排他的にすることを好みます。しかし、両方とも機能します。upB

ここで、ここで何が起こっているのかを本当に理解していることを確認してください。コードをコピーして先に進むだけではありません。それがどのように一緒にぶら下がっているのかを理解してください。

于 2013-03-01T20:57:54.323 に答える
3

その際、勝手に返却する前lowB == upBにチェックする必要があります。sortedArray[lowB] == key-1

于 2013-03-01T20:58:26.397 に答える