Ricerca binaria
Trovare un elemento in una sequenza ordinata in tempo O(log n): a ogni passo lo spazio di ricerca si dimezza, si guarda al centro e si prosegue a sinistra o a destra.
Esempio classico da primo corso di informatica. Le implementazioni sono notoriamente soggette a errori: Knuth osservò che la maggior parte delle varianti contiene sottili errori di off-by-one. Il metodo Arrays.binarySearch del JDK ha convissuto per nove anni con un bug di overflow (scoperto nel 2006). git bisect è una ricerca binaria sulla cronologia dei commit. Generalizzazione: lower_bound/upper_bound della STL di C++ trovano le posizioni di inserimento. Funziona solo su dati ordinati.