java - 在java中使用递归进行二分搜索时出现错误的值

Question

我正在尝试使用递归实现二分搜索，但我没有得到预期的正确结果。代码如下:

import java.util.*;
class BinarySearchRecursion{

    static private int searchNum(int[] array, int item){
        if(array.length >=2){
            int remainder = array.length%2;
            int splitSize = array.length/2;
            if(remainder==0){
                if(item> array[splitSize-1]){
                    int num = searchNum(Arrays.copyOfRange(array,splitSize,array.length), item);
                    return num;
                }else{
                    int num = searchNum(Arrays.copyOfRange(array,0,splitSize), item);
                    return num;
                }
            }else{
                if(array[splitSize]== item)
                    return splitSize;

                if(item> array[splitSize-1]){
                    int num = searchNum(Arrays.copyOfRange(array,splitSize,array.length), item);
                    return num;
                }else{
                    int num = searchNum(Arrays.copyOfRange(array,0,splitSize), item);
                    return num;
                }
            }
            //System.out.println(splitSize);
        }else{
            if(array[0] == item){
                System.out.println("Item exist");
                return item;
            }
            else
                return -1;
        }
        //return -1;
    }


    public static void main(String... args){
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int index = searchNum(arr, 89);
        if(index != -1){
            System.out.println("Number exist: "+ Integer.valueOf(index));
        }
        else
            System.out.println("Number does not exist in the given list.");
    }
}

我没有得到正确的项目，比如如果我搜索 8，它会给我值 2 等。我在这里做错了什么？

Answer 1

您试图在数组中搜索给定数字的索引，但由于您的递归方法不断将子数组传递给递归调用，因此索引不断变化。

例如，当您调用时

searchNum(Arrays.copyOfRange(array,splitSize,array.length), item)

当前数组的

索引splitSize将成为传递给searchNum()的新数组的索引0。

您应该始终将原始(完整)数组传递给递归调用，此外您还应该传递相关范围的第一个和最后一个索引。

代码中的另一个错误是在 if(array[0] == item) 条件中，您返回的是项目值而不是该项目的索引。

除此之外，您可能不必为数组的奇数与偶数范围的情况编写单独的逻辑。