Алгоритм двоичного поиска. Почему неправильно работает алгоритм?

Question

[Аркадий Саакян]

public static int binarySearch(int[] numbers, int left, int right, int key) {
        if (left <= right) {
            int mid = (left + right) / 2;
            int midVal = numbers[mid];
            if (midVal < key)
                return binarySearch(numbers, left, mid - 1, key);
            else if (midVal > key)
                return binarySearch(numbers, mid + 1, right, key);
            else
                return mid;
        }
        return -1;
    }

Скажите, почему иногда неправильно работает алгоритм?

Comments

[Rsa97]

Так а где минимальный набор данных, на которых алгоритм работает неправильно?
Вы учитываете, что для работы двоичного поиска массив должен быть предварительно отсортирован по возрастанию?

[Akina]

Представь, что на очередном шаге left+1=right. Тогда mid равно или left, или right (понятия не имею, как округляет Java). Теперь пусть key равен другому значению переданной границы (скажем, если mid=left, то key=numbers[right]). Произойдёт рекурсивный вызов, но передаваемые для left и right значения образуют некорректную пару, которая не пройдёт контроля left <= right.

PS. Это - НЕ двоичный поиск. В крайнем случае это его нестандартная вариация с (неудачной) попыткой оптимизации.

PS. Для исправления достаточно убрать "оптимизацию" и передавать mid как есть.

[Wataru]

Akina, это стандартная реализация, которая не виснет на массиве из двух элементов. Ибо, если mid=left, и там элемент слишком мелкий, то ничего не меняется (low становится mid, который ему и так равен).

Можно всегда выкидывать mid из рассмотрения, потому что он уже проверен и не подошел.

Answer 1

[Wataru]

Знаки в условиях перепутаны.