Неправильное значение при выполнении бинарного поиска с использованием рекурсии в 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, et c. Что я здесь не так делаю?

Answer 1

Вы пытаетесь найти индекс данного числа в массиве, но так как ваш рекурсивный метод продолжает передавать подмассивы рекурсивным вызовам, индексы продолжают изменяться.

Например, когда вы вызов

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

Индекс splitSize текущего массива станет индексом 0 нового массива, переданного в searchNum().

Вы должны всегда передавать исходный (полный) массив в рекурсивные вызовы, и, кроме того, вы должны передать первый и последний индексы соответствующего диапазона.

Другая ошибка в вашем коде в условии if(array[0] == item), где вы возвращаете значение элемента вместо индекса этого элемента.

Кроме этого, вам, вероятно, не нужно писать отдельные логики c для случая нечетного и четного диапазона массива.