Busca Binária: Comprar Informação pela Metade

Ordenar e buscar são formas de comprar informação. A ordenação paga $O(n\log n)$ uma única vez para que muitas perguntas futuras fiquem baratas. A busca binária paga uma comparação para descartar metade da incerteza que resta. Com $n={10}^6$ elementos ordenados, vinte comparações bastam para localizar qualquer valor, enquanto uma busca linear pode precisar de um milhão.

A frase é famosa, e a implementação é famigerada. Knuth (1998) registra que a primeira busca binária foi publicada em 1946, mas a primeira versão correta para todos os tamanhos só apareceu em 1962. Bentley (2000) relata que, em cursos para programadores profissionais, cerca de noventa por cento não conseguiram escrever uma busca binária correta em algumas horas. O algoritmo é antigo, curto e continua ferindo programadores com uma regularidade impressionante. Os erros vêm quase sempre de três lugares: o cálculo do meio como (lo + hi) / 2, que pode sofrer overflow; a mistura de intervalos fechados com intervalos semiabertos; e o esquecimento do invariante do laço. Este artigo começa pelo invariante, porque o invariante é o algoritmo. O código é apenas a caligrafia.

O percurso tem três partes. A primeira constrói a busca binária a partir do invariante, deduz o número de comparações e apresenta as versões da biblioteca padrão. A segunda mede a busca no MSVC e mostra que a contagem de comparações, embora correta, esconde quase todo o custo quando o vetor sai do cache (memória pequena e rápida junto ao processador). A terceira leva a mesma ideia para fora dos vetores: em vez de procurar uma posição, a busca procura a fronteira de um predicado sobre o espaço das respostas possíveis, que é o uso mais poderoso da busca binária em competições.