1

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

int binarySearch(int a[], int value, int start, int end) {
    int rHalf = (end - start) / 2 + start;
    int lHalf = rHalf + 1;
    printf("\n\n%d-%d %d-%d\n", start, rHalf, lHalf, end);
    if (start == rHalf && value == a[start]) {
        printf("start == rHalf = %d, value = %d\n", start, a[start]);
        return start;
    } else if (end == lHalf && value == a[end]) {
        printf("end == lHalf = %d, value = %d\n", end, a[end]);
        return end;
    } else if (value <= a[rHalf]) {
        binarySearch(a,value,start,rHalf);
    } else if (value >= a[lHalf]) {
        binarySearch(a,value,lHalf,end);
    }
    return -1;
}

Тип возвращаемого значения int, собственно int и возвращаем.

Но почему то даже в случае когда срабатывает один из первых двух переключаетелей - функция возвращает -1, если я убираю последнюю строку, то получаю warning на этапе компиляции и функция возвращает 0 в результате срабатывания одного из первых двух переключателей.

В основном я пишу на Java и там функция возвращает управление коду сразу после команды return, здесь же, как я понял - даже после явного вызова return выполнение функции продолжается до последней сроки.

Хотелось бы знать, почему так происходит и как это можно обойти?

UPDATE

Очевидно я задал вопрос туманно.

Я генерирую массив с помощью rand() - длину и компоненты, сортирую его и запускаю поиск. Выглядит это приблизительно так:

init();
printArr(array, size);
mergesort(array, 1, size);
printArr(array, size);
int searchValue = rand() % MAX_VALUE;
printf("\nSearch value = %d\n", searchValue);
printf("\nSearch value = %d\n", searchValue);

printf("\nindex = %d\n", binarySearch(array, searchValue, 0, size));

Я думаю, код в комментариях не нуждается, все довольно прозрачно. Дело в том, что в результате выполнения я в консоли вижу следующее:

end == lHalf = 10, value = 55 

Срабатывает второй переключатель - соответственно обязано выполниться return end, значит я должен увидеть в консоли index = 10, но выводится при этом:

index = -1

то есть управление передается коду не после return end, а после return -1.

3
  • warning у тебя потому, что компилятор предполагает, что когда-нибудь ни один из ифов не сработает 31 авг 2016 в 18:26
  • нет, после return сразу выход.
    – pavel
    31 авг 2016 в 18:26
  • «... здесь же, как я понял ...». Вы неправильно поняли. А по поводу основного вопроса – поставьте breakpoint и посмотрите что, откуда и куда. Ситуация станет яснее.
    – s8am
    31 авг 2016 в 18:26

1 ответ 1

7
} else if (value <= a[rHalf]) {
    binarySearch(a,value,start,rHalf);

Здесь вы рекурсивно вызываете binarySearch, но не возвращаете ее значение, а возвращаете -1, так как после этого вызова выполнение продолжается.

Пишите

return binarySearch(a,value,start,rHalf);
1
  • Спасибо большое, самые очевидные ошибки всегда ускользают из виду) 31 авг 2016 в 18:33

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.