整数的Java数组的二进制搜索 [英] binary search on array of integer in java

问题描述

我知道这是一个非常著名的问题，很多已经提供的答案，但我想实现我自己的Java二进制搜索算法。

I know this is a very famous question and lots of answers provided already, but I am trying to implement binary search algorithm in java of my own.

首先得到下面的编译错误，为什么？

First of all getting following compilation error, why??

此方法必须返回一个int类型的结果

This method must return a result of type int

其次这种方法如何不同于这个著名的解决方案

Second how this approach differs from 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);
}

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

Please ignore the boundary conditions and logical mistakes, as this is draft version.

推荐答案

有一个失踪返回你的binarySearch 功能。在Java中，编译器将验证所有可能的执行路径上返回正确类型的存在。在你的情况，如果所有的测试都是假的，那么执行起来的功能到底哪里没有返回值，违反了功能合同。

There is a missing return at the end of your binarySearch function. In Java, the compiler verifies that on every possible execution path a return of the right type exists. In your case, if all tests are false, then the execution rises the end of the function where there is no returned value, violating the function contract.

您算法不同于引用之一是你构建了一个新的数组，在每个'分裂'的方式。因此，我们可以说，因为你用了太多的内存，而不进行任何真正需要的是效率比较低。

Your algorithm differs from the cited one in the way that yours constructs a new array at each ‘‘split’’. So, we can say that it is relatively inefficient because you use too much memory without any real need for it.

这篇关于整数的Java数组的二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！