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