Busca binária é provavelmente o algoritmo de busca mais útil para aprender após a busca linear. Ela resolve um problema simples com uma insight poderosa: em uma lista ordenada, você não precisa examinar todos os elementos — pode eliminar metade dos candidatos a cada passo. O resultado é performance que parece mágica: encontrar um elemento entre 1 bilhão de itens em no máximo 30 comparações. Entender busca binária profundamente — não apenas a implementação, mas quando e como aplicar o princípio — é uma das habilidades mais valorizadas em entrevistas técnicas de nível sênior.
O princípio: eliminar metades
Imagine que você quer achar o número 73 numa lista ordenada de 1 a 100. Em vez de começar do 1, você pergunta: “O número do meio (50) é maior ou menor que 73?” — É menor. Então o número está na metade direita (51–100). Novo meio: 75. “75 é maior que 73?” — sim. Está na metade esquerda (51–74). Novo meio: 62. E assim por diante — em 7 comparações você encontra 73 numa lista de 100 elementos. Com busca linear, seriam até 100 comparações.
Implementação clássica
def busca_binaria(arr, alvo):
"""
Pré-requisito: arr deve estar ordenado.
Retorna o índice do alvo ou -1 se não encontrar.
Complexidade: O(log n)
"""
esquerda = 0
direita = len(arr) - 1
while esquerda <= direita:
meio = (esquerda + direita) // 2
if arr[meio] == alvo:
return meio
elif arr[meio] < alvo:
esquerda = meio + 1 # Já que arr[meio] alvo, elimina metade direita
return -1 # Não encontrado
numeros = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(busca_binaria(numeros, 23)) # Saída: 5
print(busca_binaria(numeros, 50)) # Saída: -1Cuidado com o bug clássico
O cálculo do meio tem um bug sutil em linguagens com overflow de inteiros: meio = (esquerda + direita) // 2 pode causar overflow se os índices forem muito grandes. A forma segura é: meio = esquerda + (direita - esquerda) // 2. Em Python isso não é problema (inteiros são de precisão arbitrária), mas em C, Java e outras linguagens com overflow, o bug causou falhas em implementações de livros clássicos por décadas — inclusive na biblioteca padrão do Java, corrigida em 2006.
Busca binária em problemas reais: além de achar elementos em arrays
O verdadeiro poder da busca binária está em aplicá-la em problemas que não parecem óbvios à primeira vista. O princípio funciona sempre que: existe um espaço de busca ordenado e você pode verificar se um valor candidato é “muito grande” ou “muito pequeno”. Exemplos clássicos de entrevista:
- Encontrar a raiz quadrada inteira de N: busca binária entre 0 e N/2 — candidato ao meio ao quadrado maior que N? Vai para a esquerda. Menor? Vai para a direita.
- Encontrar o mínimo num array rotacionado:
[4,5,6,7,0,1,2]— o ponto de rotação pode ser encontrado com busca binária em O(log n). - Alocação de recursos: “qual o menor número de dias para completar X tarefas com Y trabalhadores?” — busca binária na resposta, verificando se um número de dias é viável.
# Busca binária na biblioteca padrão do Python
import bisect
numeros = [1, 3, 5, 7, 9, 11, 13]
pos = bisect.bisect_left(numeros, 7)
print(pos) # Saída: 3 (índice onde 7 está ou seria inserido)
# Verificar se elemento existe
if pos < len(numeros) and numeros[pos] == 7:
print("Encontrado no índice", pos)Para uso em produção, use sempre as implementações nativas (bisect em Python, Arrays.binarySearch em Java, lower_bound em C++) — são testadas e corretas. Implemente do zero apenas para praticar ou para casos especiais.
Tem um projeto em mente?
Somos especialistas em transformar ideias em produtos digitais. Apps, sites, automações e IA — vamos construir juntos.
