⚡️ Бинарный поиск, который вы выучили, скорее всего, был неправильным.
Джон Бентли опубликовал реализацию бинарного поиска в *Programming Pearls* после того, как доказал её корректность и протестировал.
Баг прожил почти 20 лет.
Позже Джошуа Блох нашёл точно такую же ошибку в реализации бинарного поиска, которую сам написал для JDK.
Исследование 1988 года показало: корректный бинарный поиск был только в 5 из 20 учебников.
Ошибка проявляется только на массивах размером 2^30 элементов и больше.
Проблема возникает при вычислении середины:
mid = (low + high) / 2;
На очень больших массивах low + high может вызвать переполнение.
Правильнее писать так:
mid = low + (high - low) / 2;
В C такое переполнение может привести к выходу за границы массива и непредсказуемому поведению. В Java это обычно заканчивается ArrayIndexOutOfBoundsException.
Та же ошибка затрагивала mergesort и огромное количество других алгоритмов «разделяй и властвуй».
Джон Бентли опубликовал реализацию бинарного поиска в *Programming Pearls* после того, как доказал её корректность и протестировал.
Баг прожил почти 20 лет.
Позже Джошуа Блох нашёл точно такую же ошибку в реализации бинарного поиска, которую сам написал для JDK.
Исследование 1988 года показало: корректный бинарный поиск был только в 5 из 20 учебников.
Ошибка проявляется только на массивах размером 2^30 элементов и больше.
Проблема возникает при вычислении середины:
mid = (low + high) / 2;
На очень больших массивах low + high может вызвать переполнение.
Правильнее писать так:
mid = low + (high - low) / 2;
В C такое переполнение может привести к выходу за границы массива и непредсказуемому поведению. В Java это обычно заканчивается ArrayIndexOutOfBoundsException.
Та же ошибка затрагивала mergesort и огромное количество других алгоритмов «разделяй и властвуй».