Что я делаю не так в моем двоичном поисковом коде C? - PullRequest
Новая
       21

Что я делаю не так в моем двоичном поисковом коде C?

0 голосов
/ 16 июня 2020
• 1000 Курсор застревает, когда я меняю значение на худшее, например на первую позицию.

Я знаю, что двоичный поиск имеет худший вариант O (log n), поэтому он не займет много времени. Я что делаю неправильно? 

#include <stdio.h>

int binary_search(int arr[], int left, int right, int data){
    // condition that runs only if true
    while(left <= right){
        int mid = (left + right) / 2;
        if(data == arr[mid]){
            return mid;
        }

        if(data > arr[mid]){
            binary_search(arr, mid+1, right, data);
        }

        binary_search(arr, left, mid-1, data);
    }
    return -1;
}

void main(){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int result = binary_search(arr, 0, (sizeof(arr)/sizeof(arr[0]) - 1), 2);
    (result == -1) ? printf("There was no record found\n") : printf("Your record was found at position %d\n", result+1);
}

Ответы [ 2 ]

2 голосов
/ 16 июня 2020

Вы запускаете бесконечную рекурсию, некорректно возвращаясь из функции. Если вы вызываете binary_search(arr, mid+1, right, data); рекурсивно, вам необходимо распространить возвращаемое значение обратно в вызывающую функцию.

Кроме того, это не имеет отношения к вашей проблеме, но в C void main() технически незаконно, даже если вы можете не получить явных ошибок. main () всегда должен возвращать int. 

#include <stdio.h>

int binary_search(int arr[], int left, int right, int data){
    // condition that runs only if true
    while(left <= right){
        int mid = (left + right) / 2;
        if(data == arr[mid]){
            return mid;
        }

        if(data > arr[mid]){
            return binary_search(arr, mid+1, right, data);
        }

        return binary_search(arr, left, mid-1, data);
    }
    return -1;
}

int main(void){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int result = binary_search(arr, 0, (sizeof(arr)/sizeof(arr[0]) - 1), 2);
    (result == -1) ? printf("There was no record found\n") : printf("Your record was found at position %d\n", result+1);

    return 0;
}
1 голос
/ 16 июня 2020

Ваш код не работает, потому что ваша рекурсивная функция ничего не возвращает, если в первой итерации data не равно arr[mid]. Таким образом, в таком случае у вас будет бесконечная рекурсия.

Но в любом случае для профессионального программиста код очень и очень слабый.

Например, ваша функция не может быть вызвана для постоянный массив. (Требуется ли еще одна функция с другим именем?)

Функция должна иметь только три параметра 

return_type binary_search( const int a[], size_t n, int data );

Если функция возвращает индекс целевого элемента, то ее тип возврата должен быть size_t, потому что, как правило, тип int может быть неспособен вместить значение выражения sizeof( a ) / sizeof( *a ).

Если функция только проверяет, существует ли данное значение в массиве, она должна возвращать либо 0 или 1 и его тип возврата должен быть либо int, либо _Bool.

Если функция должна возвращать позицию целевого значения, тогда она должна возвращать первую позицию элемента с целевое значение так же, как и стандартный алгоритм std :: lower_bound в C ++.

Не рекомендуется копировать тот же недостаток стандартной C функции bsearch, которая в целом не возвращает позицию первого элемента с целевым значением.

Вы не должны использовать оператор == для сравнения значений (хотя функции сравнения в C используют этот оператор), потому что, например, для плавающих чисел вы можете получить неправильный результат. Следует использовать только оператор <. </p>

Итак, предположим, что ваша функция работает с массивами с типом элемента int и оператором <. Но что делать, если пользователь хочет использовать собственную функцию сравнения элементов массива? </p>

И вторая проблема, если пользователь собирается использовать массив с типом элемента long long или массив структур нужно ли ему тратить свое время, чтобы написать еще одну функцию двоичного поиска?

Мой совет: никогда не выполняйте никаких заданий на собеседовании. Игнорируйте фирмы, которые пытаются манипулировать вами и вашим временем. Интервью - это разговор равных партнеров. В простом разговоре легко понять «кто есть кто» при условии, что вы сами являетесь квалифицированным программистом. :)

...