Двоичный поиск
Поиск элемента в отсортированной последовательности за O(log n): на каждом шаге пространство поиска делится пополам — смотрим в середину и идём влево или вправо.
Классический пример из первого курса. Реализации славятся ошибками — Кнут отмечал, что в большинстве вариантов скрываются тонкие ошибки на единицу. В JDK у Arrays.binarySearch девять лет жила ошибка переполнения (обнаружена в 2006 году). git bisect — это двоичный поиск по истории коммитов. Обобщение: lower_bound/upper_bound в STL C++ находят позиции вставки. Работает только на отсортированных данных.