Wyszukiwanie binarne
Znajdowanie elementu w posortowanej sekwencji w czasie O(log n): w każdym kroku przestrzeń poszukiwań się zmniejsza o połowę — sprawdzasz środek i idziesz w lewo albo w prawo.
Klasyk z pierwszego roku informatyki. Implementacje są osławione z błędów — Knuth zauważył, że większość wariantów ma subtelne pomyłki o jeden. W JDK metoda Arrays.binarySearch miała błąd przepełnienia przez 9 lat (wykryty w 2006 roku). git bisect to wyszukiwanie binarne po historii commitów. Uogólnienie: lower_bound i upper_bound w STL C++ wyznaczają pozycje wstawienia. Działa wyłącznie na danych posortowanych.