Busca binária (binary search) em Python
Nesta lição, você vai implementar a busca binária para encontrar rapidamente um valor em uma lista ordenada.
Introdução
O problema
Procurar um valor em uma lista de um milhão de itens, olhando um por um, pode custar um milhão de comparações. Quando a lista está ordenada, dá para fazer bem melhor: umas 20 comparações bastam, porque cada verificação descarta metade do que sobrou.
Pense assim
A busca binária é como procurar uma palavra em um dicionário de papel. Você abre no meio, vê se a palavra vem antes ou depois daquela página e joga fora a metade que não pode contê-la. Depois repete com a metade que sobrou até chegar na palavra.
low, high = 0, len(values) - 1📖 As páginas que ainda faltam procurarmiddle = (low + high) // 2👆 Abra no meiolow = middle + 1➡️ A palavra vem depois: descarte a primeira metadehigh = middle - 1⬅️ A palavra vem antes: descarte a segunda metadeA busca binária encontra um valor em uma lista ordenada comparando-o várias vezes com o elemento do meio e descartando a metade que não pode contê-lo. Ela leva O(log n) passos.
Pontos-chave
lowehighmarcam a parte da lista que ainda pode conter o alvo.middle = (low + high) // 2escolhe o índice do meio dessa parte.- Se
values[middle] < target, o alvo está à direita, entãolow = middle + 1; senão,high = middle - 1. while low <= high:para quando o intervalo fica vazio, e a função devolve-1para"não encontrado".- Para 17, a busca verifica 12, depois 25, depois 17: três comparações em vez de quatro.
Quando usar?
- Buscar em dados grandes e ordenados: IDs, dicionários, logs ordenados.
- Descobrir onde inserir um valor para a lista continuar ordenada.
- Jogos de adivinhação e qualquer problema em que a resposta pode ser estreitada com
"maior"ou"menor".
Quando não é preciso
- Os dados não estão ordenados: ordenar só para buscar uma vez custa mais que uma busca linear.
- Listas pequenas ou buscas isoladas:
inou um dicionário é mais simples; para muitas buscas por chave, um dict ou set é ainda mais rápido.
Visualizador de Busca binária (binary search) em Python
O(log n)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))
Resultado da execução
3
Explicação do código
As variáveis low e high definem o intervalo de busca que resta. Se o elemento do meio for menor que o valor procurado, o algoritmo descarta a metade esquerda com low = middle + 1; caso contrário, descarta a metade direita. A complexidade de tempo é O(log n), desde que a lista de entrada já esteja ordenada.
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Usar < em vez de <= no laço
Com low < high, um alvo na última posição restante nunca é verificado.
while low < high:
while low <= high:
Não passar do meio
low = middle pode repetir o mesmo meio para sempre.
low = middle
low = middle + 1
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
- Tempo de Produção na Fábrica Encontre o menor tempo em que máquinas paralelas conseguem finalizar uma quantidade alvo de itens. Médio
- Median of Two Sorted Arrays Find the median of two sorted lists combined. Difícil