java - 在java中对整数数组进行二进制搜索

Question

我知道这是一个非常有名的问题并且已经提供了很多答案，但我正在尝试在我自己的 java 中实现二进制搜索算法。

首先出现以下编译错误，为什么？？

This method must return a result of type int

其次，这种方法与 this famous solution 有何不同？

public static int binarySearch(int test[], int num){

    int midLength = test.length/2;
    int fullLength = test.length;

    if(num > test[midLength]){
        int newArray[] = new int[fullLength - midLength];
        for (int j = 0; j<= midLength ; j++){
            newArray[j] = test[midLength + j];

        }
        return binarySearch(newArray, num);
    }
    else if(num < test[midLength]){
        int newArray[] = new int[midLength];
        for (int j = 0; j<= fullLength - midLength ; j++){
            newArray[j] = test[j];

        }
        return binarySearch(newArray, num);
    }
    else if(num == test[midLength]){
        return test[midLength];
    }

}

public static void main(String[] args) {
    int test[] = {2,8,1,6,4,6};
    Arrays.sort(test);
    int num = ArraysTest.binarySearch(test, 1);
    System.out.println(num);
}

请忽略边界条件和逻辑错误，因为这是草案版本。

Answer 1

binarySearch 函数末尾缺少一个return。在 Java 中，编译器验证在每个可能的执行路径上是否存在正确类型的返回。在您的情况下，如果所有测试都是假的，那么执行将上升到没有 returned 值的函数末尾，这违反了函数契约。

您的算法与引用的算法的不同之处在于您的算法在每次“拆分”时构造一个新数组。因此，我们可以说它是相对低效的，因为您使用了太多内存而实际上并不需要它。