Блог

Главная - Вопросы по программированию - Двоичный поиск, выдающий неверный вывод

Двоичный поиск, выдающий неверный вывод

#java #binary-search

#java #двоичный поиск

Вопрос:

Для входного двоичного поиска (2, A, 9), где A = {2,6,7,7,11,15,25,37,45}, программа выдает вывод «Not Present», когда он должен выдавать «Present». Что я делаю не так?

Вот мой код:

 String binarySearch(int x, int[] A, int n)
{
    if(n==0)
        return ("Not present");
    else
    {
        int mid = n/2;
        if(x==A[mid])
            return ("Present");
        else if (x<A[mid])
            binarySearch(x, Arrays.copyOfRange(A,0,mid),mid);
        else
            binarySearch(x, Arrays.copyOfRange(A,mid,n),n-mid);

        return ("Not present");
    }
}

Комментарии:

1. Потому что ваша последняя строка возвращает Not present независимо от того, что возвращают рекурсивные вызовы.

2. Используйте фигурные скобки, и у вас не будет подобных ошибок.

3. Только что понял. Сейчас кажется таким глупым вопросом. Спасибо!

Ответ №1:

Отсутствующий return оператор в рекурсивном вызове:

 else if (x<A[mid])
    return binarySearch(x, Arrays.copyOfRange(A,0,mid),mid);
else
    return binarySearch(x, Arrays.copyOfRange(A,mid,n),n-mid);

Ответ №2:

вам нужно вернуть рекурсивный вызов 

   String binarySearch(int x, int[] A, int n)
   {
        if(n==0)
           return ("Not present");
        else
           {
             int mid = n/2;
             if(x==A[mid])
                 return ("Present");
              else if (x<A[mid])
                  return  binarySearch(x, Arrays.copyOfRange(A,0,mid),mid);
               else
                  return binarySearch(x, Arrays.copyOfRange(A,mid,n),n-mid);


       }
       }

Ответ №3:

Вы забыли добавить return оператор вместе с else if вызовами рекурсии, потому что теперь он просто вернет Present единственное, если x найдено в середине, остальные вызовы работают, но ничего не возвращают, так что так и должно быть

 static String binarySearch(int x, int[] A, int n)
{
    if(n==0)
        return ("Not present");
    else
    {
        int mid = n/2;
        if(x==A[mid])
            return ("Present");
        else if (x<A[mid])
            return binarySearch(x, Arrays.copyOfRange(A,0,mid),mid);
        else
            return binarySearch(x, Arrays.copyOfRange(A,mid,n),n-mid);

    }
}