Бинарный поиск, который вы изучали, мог быть неправильным.



Джон Бентли опубликовал свою реализацию бинарного поиска в Programming Pearls, где доказал её правильность, но ошибка прожила почти 20 лет. Позже Джошуа Блох обнаружил ту же проблему в своём варианте для JDK.

Исследование 1988 года показало, что корректный бинарный поиск был только в 5 из 20 учебников. Ошибка возникает на массивах с размером 2^30 элементов и больше, когда mid вычисляется как:

mid = (low + high) / 2;

Здесь low + high может переполниться. Верный подход:

mid = low + (high - low) / 2;

В C это может вызвать выход за границы массива, а в Java — исключение ArrayIndexOutOfBoundsException. Аналогичная ошибка затрагивала и другие алгоритмы «разделяй и властвуй», например, mergesort.
Просмотры: 5 880
Открыть в MAX Сообщить о неточности

Репосты публикации

Публикация канала

Сообщить о неточности

Опишите, что нужно исправить. Если есть источник, добавьте ссылку.

Вы покидаете datool.ru

Ссылка ведёт на внешний сайт. datool.ru не отвечает за его содержимое — проверьте адрес, прежде чем вводить пароли или платёжные данные.

Переход через 10 с

Перейти