Member 13241712 Ответов: 3

Рекурсивный бинарный поиск в C

Моя функция не работает, мне нужно предварительно сформировать рекурсивный двоичный поиск, который возвращает указатель на местоположение числа, которое я искал, или null, если оно не существует.

код: 
int* binsearch(int arr[], int low, int size, int *p)
{
    int mid;
 
    mid = (low + size)/2;
    if (arr[mid] == *p) // found result
    {
        *p = arr[mid];
	return p; 
    }
    
    if (size <= 1) // meaning the number is not in the array
    {
      printf("Number not found\n");
      return NULL;
    }
    
    if (arr[mid] > *p) // if its on the left half of the array
    {
        binsearch(arr, low, size/2, p);
    }
    if (arr[mid] < size) // if its on the right half of the array
    {
        binsearch(arr+mid, mid+1, size/2, p);
    }
    
}


Что я уже пробовал:

выложил код, который я пробовал, и еще пару вариаций, но, похоже, ничего не работает

3 Ответов

Рейтинг:
1

Patrice T

Цитата:
Моя функция не работает

Это не информативно. Также будет полезен пример вызова функции woukd.
В вашем коде есть множество проблем:
binsearch(arr, low, size/2, p);
binsearch(arr+mid, mid+1, size/2, p);

В зависимости от size от arr будучи нечетным или четным, ваш код терпит неудачу на size/2 И это всего лишь 1 очко неудачи.

Когда вы не понимаете, что делает ваш код или почему он делает то, что делает, ответ таков: отладчик.

Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволяет вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения, это невероятный инструмент обучения.

Отладчик-Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010-YouTube[^]
Отладчик здесь для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.

Рейтинг:
1

Klaus-Werner Konrad

Вы не возвращаете указатель из ваших рекурсивных вызовов binsearch ()...

Рейтинг:
0

OriginalGriff

Компиляция не означает, что ваш код верен! :смеяться:
Подумайте о процессе разработки как о написании письма: успешная компиляция означает, что вы написали письмо на правильном языке - например, на английском, а не на немецком, - а не то, что письмо содержало сообщение, которое вы хотели отправить.

Итак, теперь вы входите во вторую стадию разработки (на самом деле это четвертая или пятая, но к более ранним стадиям вы придете позже): тестирование и отладка.

Начните с рассмотрения того, что он делает и чем это отличается от того, что вы хотели. Это важно, потому что это дает вам информацию о том, почему он это делает. Например, если программа предназначена для того, чтобы позволить пользователю ввести число, а он удваивает его и печатает ответ, то если ввод / вывод был таким:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16
Тогда совершенно очевидно, что проблема заключается в бите, который удваивает его-он не прибавляет себя к себе или умножает его на 2, он умножает его на себя и возвращает квадрат входного сигнала.
Таким образом, вы можете посмотреть на код, и очевидно, что он где-то здесь:
private int Double(int value)
   {
   return value * value;
   }

Как только у вас появится идея, что может пойти не так, начните использовать отладчик, чтобы выяснить почему. Поставить точку останова на строке:
mid = (low + size)/2;

и запустите свое приложение. Подумайте о том, что должна делать каждая строка кода перед ее выполнением, и сравните это с тем, что она на самом деле делала, когда вы использовали кнопку "шаг вперед" для выполнения каждой строки по очереди. Он сделал то, что вы ожидали? Если да, то переходите к следующей строке.
Если нет, то почему? Чем это отличается?

Это навык, и его стоит развивать, поскольку он помогает вам как в реальном мире, так и в развитии. И, как и все навыки, он совершенствуется только при использовании!

Да, я, наверное, мог бы сказать вам, в чем "проблема" - но сделать это самому несложно, и при этом вы узнаете что-то действительно стоящее!