2

День добрый. Реализовал рекурсивный двоичный поиск, но время от времени переполняется стек. В чем проблема?

int bin_search(vector<int> & arr, int left, int right, int number) {
    int mid = left / 2 + right / 2;

    if (left > right) {
        return -1;
    }

    if (left <= right) {
        if (number == arr[mid]) {
            return mid;
        }
        else if (number > arr[mid]) {
            bin_search(arr, mid + 1, right, number);
        }
        else {
            bin_search(arr, left, mid - 1, number);
        }
    }
}

1 ответ 1

3

Первое, то нашел - это следующая строка

int mid = left / 2 + right / 2;

она не всегда ищет "середину". допустим, что left и right равны 1, тогда mid будет равно 0. А это не совсем то, что ожидается. Если взять два других нечетных числа, то будет такая же ситуация или около того. Например, при 3 и 5, середина у Вас получается 3 (1 + 2)

при двух 1 эта строка скорее всего и приводит к зацикливанию.

Как избежать подобных ошибок? добавьте в список #include <cassert>, а в коде после данного вычисления добавьте такое

assert(mid >= left);
assert(right>=mid);

и ошибка сама всплывет.

Ваш ответ

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

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