1

配列と配列をソートするメソッドを作成しましたが、配列にバイナリ検索メソッドを実装する方法にまだこだわっています。また、メインクラスの配列から二分探索メソッドを呼び出す必要があります。

public class Search {

public static boolean binarySearch(int[] array, int value) {
    return binarySearchHelper(array, value, 0, array.length);
}

private static boolean binarySearchHelper(int[] array, int value, int low, int high) {
    if (low <= high) {
        int mid = (low + high) / 2;
        if (value == array[mid]) {
            return true;
        } else if (value < array[mid]) {
            return binarySearchHelper(array, value, low, mid - 1);
        } else {
            return binarySearchHelper(array, value, mid + 1, high);
        }
    }
    return false;
}

public static boolean linearSearch(int[] array, int value) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == value) {
            return true;
        } else if (array[i] > value) {
            return false;
        }
    }
    return false;
}

そしてメインはこちら

import java.util.Random;
import java.util.Arrays;

public class Test {

    public static void main(String[] args) {

        //System.nanoTime() will give me the current time (it's like looking at the clock)
        //I'll save the current time right (immediately) before I start the thing I want to time
        long start = System.nanoTime();

        long elapsed = System.nanoTime() - start;
        Random value = new Random();
        int size = 2000;
        int max = 5000;
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = value.nextInt();
        }
        Arrays.sort(array);
        for (int i = 100; i < 2000; i+=100) {
            start = System.nanoTime();
            for ( int j = 0; j < 2000; j++){
                Search.binarySearch(array, value.nextInt());
            }
        }
        elapsed = System.nanoTime() - start;
        System.out.println("Total time elapsed is: "+ elapsed);
    }
}
4

1 に答える 1

1

あなたの二分探索法自体は今のところ私には良さそうです。

あなたの問題はあなたのmain方法にあります：

for ( int j = 0; j < 2000; j++){
    return array;
}

まず、returnステートメントを使用すると、メソッドは終了して呼び出し元に戻ります。このため、ループの反復が 1 回しか実行されず、これは意図した動作ではない可能性があります。

ただし、これはとにかくここでは発生しません。このステートメントをコンパイルすることはできません。Javamainメソッドの戻り値の型は常にvoidreturnです。これは、ステートメントを使用しても値を返すことができないことを意味します。

あなたはベンチマークを作成しようとしていると思うので、とにかく検索の結果にはあまり関心がなく、実行にかかる時間だけに関心があるでしょう。

これを実現するには、それを呼び出して結果を破棄してみませんか?

for ( int j = 0; j < 2000; j++){
    Search.binarySearch(array, value.nextInt());
}

補足として、valueへの参照を保持する変数の最適な名前ではない可能性があります。Randomこれは、その中に何が含まれているかがわからないためです。valueGeneratorまたはrandom、より良い選択である可能性があります。このヒントは、変数がインスタンス化されている場所が常に明確であるとは限らない大規模なプロジェクトで特に便利です。

于 2015-06-03T22:17:21.670 に答える