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语句时结束并返回给调用者。因此，它只会执行循环的一次迭代，这可能不是您想要的行为。

然而，这无论如何都不会发生在这里——你将无法编译这个语句。Javamain方法始终具有返回类型void，这意味着您在使用该return语句时不能返回任何值。

由于我假设您正在尝试创建基准测试，因此您可能对搜索结果并不真正感兴趣，您只对执行它需要多长时间感兴趣。

为了实现这一点，你为什么不直接调用它并丢弃结果呢？

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

在旁注中，value可能是包含对 的引用的变量的次优名称Random，因为它不会告诉您其中的内容 -valueGenerator或者random可能是更好的选择。对于较大的项目，这个技巧可能特别方便，因为变量的实例化位置并不总是很明显。

于 2015-06-03T22:17:21.670 回答