Возможный дубликат:
Каковы подводные камни при реализации бинарного поиска?
Я просматривал страницу Википедии для Двоичный поиск и наткнулся на цитату Кнута ниже:
«Хотя основная идея бинарного поиска сравнительно проста, детали могут оказаться на удивление сложными».
Я помню, как реализовал несколько бинарных поисков в рамках моего учебного плана по компьютерным наукам, но не помню, чтобы это было ужасно сложно. Тем не менее, в этой статье говорится, что 90% опрошенных специалистов не могут заставить его работать через несколько часов. Я хотел бы предположить, что это не потому, что они ужасные программисты, а потому, что есть крайние случаи, которые не учитываются наивными реализациями.
Какие детали имеет в виду Кнут? Какие распространенные ошибки следует учитывать при реализации алгоритма бинарного поиска?
Обратите внимание, что я читал статью Блоха об ошибке Programming Pearls (переполнение int для средней точки). Что-нибудь еще?
