0

10 intの配列があり、バイナリ検索を使用して数値を検索していると仮定します。たとえば、数値を考えてみましょう。

1 2 3 4 5 6 7 8 9 10

そして私はこの方法を使用しています

static void binarySearch(int n, int[] a, int low, int high)
    {
        int mid = (high + low) / 2;
        if(low > high)
            System.out.println(n+" was not found after "+counter+" comparisons");
        else if(a[mid] == n)
        {
            counter++;
            System.out.println(n+" was found at position "+mid+" after "+counter+" comparisons");
        }            
        else if(a[mid] < n)
        {
            counter++;
            binarySearch(n, a, mid+1, high);
        }            
        else
        {
            counter++;
            binarySearch(n, a, low, mid-1);
        }            
    }

メソッドbinarySearch（5、a、0、a.lenght）またはbinarySearch（5、a、0、a.lenght-1）を呼び出す適切な方法は何ですか

私は彼らが両方とも番号を見つけることを知っていますが、彼らは異なるインデックスでそれを見つけるでしょう。したがって、より多くの比較を行う

4

3 に答える 3

2

正しい方法は、このメソッドを避け、標準のArrays.binarySearch()メソッドを使用することです。これには、文書化されるという大きな利点と、結果を System.out に出力するのではなく結果を返すという大きな利点があります (これにより、使い物にならない）。

于 2012-05-27T17:11:57.607 に答える
1

さて、いくつかのテストをしましょうか。

まず、配列内の各数値を検索してみましょう。我々が得る：

binarySearch(i, array, 0, array.length);

1 was found at position 0 after 3 comparisons
2 was found at position 1 after 4 comparisons
3 was found at position 2 after 2 comparisons
4 was found at position 3 after 3 comparisons
5 was found at position 4 after 4 comparisons
6 was found at position 5 after 1 comparisons
7 was found at position 6 after 3 comparisons
8 was found at position 7 after 4 comparisons
9 was found at position 8 after 2 comparisons
10 was found at position 9 after 3 comparisons
Average: 2.9 comparisons

binarySearch(i, array, 0, array.length - 1);

1 was found at position 0 after 3 comparisons
2 was found at position 1 after 2 comparisons
3 was found at position 2 after 3 comparisons
4 was found at position 3 after 4 comparisons
5 was found at position 4 after 1 comparisons
6 was found at position 5 after 3 comparisons
7 was found at position 6 after 4 comparisons
8 was found at position 7 after 2 comparisons
9 was found at position 8 after 3 comparisons
10 was found at position 9 after 4 comparisons
Average: 2.9 comparisons

ご覧のとおり、分散は表示されますが、平均は一定のままです。次に、より大きな数をテストしましょう。

100000 items
binarySearch(i, array, 0, array.length);
Average: 15.68946 comparisons
binarySearch(i, array, 0, array.length - 1);
Average: 15.68946 comparisons

200000 items
binarySearch(i, array, 0, array.length);
Average: 16.689375 comparisons
binarySearch(i, array, 0, array.length - 1);
Average: 16.689375 comparisons

500000 items
binarySearch(i, array, 0, array.length);
Average: 17.951464 comparisons
binarySearch(i, array, 0, array.length - 1);
Average: 17.951464 comparisons

したがって、平均的には、どちらの方向にも進みません。慣習のために、排他的な上限バージョンを使用することをお勧めします。binarySearch(i, array, 0, array.length);

于 2012-05-27T17:12:51.373 に答える
0

質問は次のように定式化できます。境界は、右を含む[low, high]か、右を含まない[low, high)ですか? 右排他形式には、ダイクストラによって「設立された」長いコンピュータ サイエンスの伝統があります。また、もう少しエレガントに思えます（a.length-1ではなくa.length）。

しかし、あなたの関数では、それは [low, high], a.length-1 です。

于 2012-05-27T17:28:52.527 に答える