Algoritmos em Python

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.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

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.

Do dicionário de papel ao código
low, high = 0, len(values) - 1📖 As páginas que ainda faltam procurar
middle = (low + high) // 2👆 Abra no meio
low = middle + 1➡️ A palavra vem depois: descarte a primeira metade
high = middle - 1⬅️ A palavra vem antes: descarte a segunda metade
Cada comparação corta pela metade o que sobra, então até listas enormes precisam de poucos passos.
Em uma frase

A 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

  1. low e high marcam a parte da lista que ainda pode conter o alvo.
  2. middle = (low + high) // 2 escolhe o índice do meio dessa parte.
  3. Se values[middle] < target, o alvo está à direita, então low = middle + 1; senão, high = middle - 1.
  4. while low <= high: para quando o intervalo fica vazio, e a função devolve -1 para "não encontrado".
  5. 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: in ou 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

Executar código →
main.py
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))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Usar < em vez de <= no laço

Com low < high, um alvo na última posição restante nunca é verificado.

Problema
while low < high:
Correção
while low <= high:

Não passar do meio

low = middle pode repetir o mesmo meio para sempre.

Problema
low = middle
Correção
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.

Todos os desafios