Дихотомия

Довольно любопытно, что Двоичный поиск имеет репутацию трудного для реализации и понимания алгоритма.

В "The Art of Computer Programming" Дональда Кнута сообщается, что двоичный поиск впервые вызвал дискуссию в 1946 году, и вплоть до 1962 г. (!) никому не удавалось опубликовать алгоритм, корректно работающий с массивами длины, отличной от 2^n - 1.