Busca binária — algoritmo, complexidade de tempo e código

A busca binária é uma forma rápida de encontrar um valor alvo em uma lista ordenada. Você verifica o item do meio, descarta metade dos valores restantes e repete. Se a lista não estiver ordenada, essa lógica não funciona.

Em uma lista em ordem crescente, a regra é simples: se o valor do meio for menor que o alvo, procure à direita; se for maior, procure à esquerda. Como o intervalo continua diminuindo pela metade, a busca binária roda em tempo $O(\log n)$.

Como a busca binária funciona em uma lista ordenada

Use esta lista ordenada:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Suponha que o alvo seja $31$.

Comece com o intervalo completo. O valor do meio é $24$. Como $31 > 24$, tudo à esquerda de $24$ pode ser descartado, então a busca continua em

$$[31, 39, 45, 52]$$

Agora o valor do meio é $39$. Como $31 < 39$, tudo à direita de $39$ pode ser descartado, então o intervalo passa a ser

$$[31]$$

Agora o valor do meio é $31$, então a busca para. A ideia importante não é só que o alvo foi encontrado. Em duas comparações, o intervalo de candidatos caiu de $9$ valores para $1$.

Por que a busca binária é $O(\log n)$

Cada comparação elimina cerca de metade dos candidatos restantes. Depois de um passo, restam cerca de $n/2$ itens. Depois de dois passos, restam cerca de $n/4$. Depois de $k$ passos, o tamanho restante é aproximadamente

$$\frac{n}{2^k}$$

A busca termina quando essa quantidade é aproximadamente $1$, então o número de passos satisfaz

$$2^k \approx n$$

Aplicando $\log_2$ nos dois lados, obtemos

$$k \approx \log_2 n$$

É por isso que a busca binária escala bem. Uma busca linear pode precisar de até $n$ verificações, mas a busca binária só precisa de verificações suficientes para continuar dividindo o intervalo pela metade.

Exemplo de código de busca binária

Aqui está uma versão iterativa padrão em Python: