测试Java中二分查找的效率

Question

我正在尝试测试java中大型排序数组的二分搜索的时间效率。

这是我正在使用的二分搜索方法，它接受搜索键和数组。

public int binarySearch(int[] a, int k) {
    int l = 0;
    int r = a.length - 1;

    int m = 0;

    while (l <= r) {
        m = (l+r)/2;
        if (k == a[m]) {
            return m;
        }
        else if (k < a[m]) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return -1;
}

我认为以编程方式创建数组可能会导致效率开销。因此，我尝试将大型数组初始化为常量并在程序中使用它。

我尝试了 Array 和 ArrayList，如下所示。

public static int D10000[] = {0, 1, 2, 3, ..... 10000};

public static ArrayList<Integer> D10000 = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5, ...... 10000);

我收到以下编译错误，因为数组大小太大。

Information:java: The system is out of resources. 
Information:java: Consult the following stack trace for details.
Information:java:   at com.sun.tools.javac.code.Type.map(Type.java:220)
Information:java: Errors occurred while compiling module 'SearchAlgo'
Information:javac 1.8.0_144 was used to compile java sources
Information:21/10/17, 12:02 PM - Compilation completed with 1 error and 0 warnings in 1s 481ms 
Error:java: java.lang.StackOverflowError

实现这一目标的最佳方法是什么？

Answer 1

以下是解决您的问题所需的几个步骤。

1）设置初始化大数组的方法：

您可以使用一个方法在主方法中调用一次，而不是手动执行，这将节省您大量的时间。 以下是初始化大型数组的示例解决方案：

    public static int[] generateLargeArraySorted(int size){
       int[] arr = new int[size];
       for(int i = 0; i < size; i++){
          arr[i] = i;
       }
       return arr;
    }

2）在你的main方法中实现这个方法

在此步骤中，您可以在 main 方法中调用新方法来生成数组，如下所示：

public static void main(String[] args){
    int sizeValue = 10000;
    int[] largeArr = generateLargeArraySorted(sizeValue);
    int key = 5000;
    // rest of the code

}

3) 为测试效率的方法计时

在此步骤中，您现在需要测试二分搜索的时间/效率，您可以使用 System.nanoTime() 来实现此目的，它将报告所需的时间（以 纳秒 为单位）：

public static void main(String[] args){
    int sizeValue = 10000;
    int[] largeArr = generateLargeArraySorted(sizeValue);
    int key = 5000;
    // Testing the efficiency
    long timeStarted = System.nanoTime();
    int resultIndex = binarySearch(largeArr, key);
    long timeEnded = System.nanoTime();
    long totalTime = timeEnded - timeStarted;
    System.out.println("Index of the searched key value: " + resultIndex);
    System.out.println("Search efficiency: " + totalTime + " nanoseconds");
}

应用完所有 3 个步骤后，您现在应该已经有了工作代码。 祝你好运！