Программисты РФ

IT и технологии · 4 августа 2026 г.

Открыть канал в MAX

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

Бинарный поиск, который вы изучали, мог быть неправильным. Джон Бентли опубликовал свою реализацию бинарного поиска в 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.