Busca binária: por que dividir ao meio funciona

Procurar um valor em uma lista de um bilhão de itens parece trabalho de sobra. Com a lista ordenada, bastam cerca de 30 comparações. Este texto mostra por quê.

A ideia: descartar metade a cada passo

Pense em procurar uma palavra num dicionário de papel. Você não começa na primeira página: abre no meio, vê se a palavra vem antes ou depois, e descarta a metade que não serve. Depois repete com a metade que sobrou. A busca binária faz exatamente isso, mas com uma lista ordenada.

def busca_binaria(lista, alvo):
    inicio, fim = 0, len(lista) - 1
    while inicio <= fim:
        meio = (inicio + fim) // 2
        if lista[meio] == alvo:
            return meio
        elif lista[meio] < alvo:
            inicio = meio + 1   # descarta a metade esquerda
        else:
            fim = meio - 1      # descarta a metade direita
    return -1                   # não encontrou

Por que é tão rápida

A cada passo, o espaço de busca cai pela metade. Quantas vezes dá para dividir n por 2 até sobrar um único elemento? Cerca de log₂(n) vezes. Compare com a busca linear, que no pior caso olha todos os itens:

Pré-requisito. A lista precisa estar ordenada. Ordenar custa mais do que uma busca linear (da ordem de n log n), então a busca binária compensa quando você faz muitas buscas na mesma lista.

Um erro que ficou escondido por anos

Na linha meio = (inicio + fim) // 2 existe uma armadilha. Em linguagens com inteiros de tamanho fixo (como Java e C), a soma inicio + fim pode estourar o limite do tipo quando a lista é enorme. A forma segura é inicio + (fim - inicio) // 2.

Em Python isso não acontece, porque os inteiros não têm tamanho fixo. Mas o erro existiu em implementações muito usadas, incluindo a biblioteca padrão do Java, e só foi divulgado em 2006.

Resumo

• Exige uma lista ordenada.
• Faz no máximo cerca de log₂(n) comparações.
• Os detalhes (limites, estouro de inteiro) é que fazem a implementação funcionar de verdade.

Para ir além: Cormen, Leiserson, Rivest e Stein, Algoritmos: Teoria e Prática.