Busca Binaria em Python: Como Implementar e Quando Usar

O que e Busca Binaria?

Busca binaria e um dos algoritmos mais eficientes para encontrar um elemento em uma colecao ordenada. Em vez de verificar cada elemento um por um (busca linear, O(n)), a busca binaria divide a colecao ao meio a cada passo, alcancando complexidade O(log n).

Na pratica, isso significa que em uma lista com 1 milhao de elementos, a busca binaria precisa de no maximo 20 comparacoes para encontrar qualquer elemento — contra ate 1 milhao na busca linear.

Antes de comecar, certifique-se de dominar listas em Python e entender algoritmos de ordenacao, ja que busca binaria exige dados ordenados.

Busca Linear vs Busca Binaria

Para entender por que busca binaria e tao poderosa, vamos comparar:

Busca Linear

def busca_linear(lista, alvo):
    for i, elemento in enumerate(lista):
        if elemento == alvo:
            return i
    return -1

# Verifica cada elemento, um por um
numeros = list(range(1, 1_000_001))
resultado = busca_linear(numeros, 999_999)
# Precisa verificar 999.999 elementos!

Busca Binaria

def busca_binaria(lista, alvo):
    esquerda = 0
    direita = len(lista) - 1

    while esquerda <= direita:
        meio = (esquerda + direita) // 2

        if lista[meio] == alvo:
            return meio
        elif lista[meio] < alvo:
            esquerda = meio + 1
        else:
            direita = meio - 1

    return -1

# Divide ao meio a cada passo
numeros = list(range(1, 1_000_001))
resultado = busca_binaria(numeros, 999_999)
# Precisa de apenas ~20 comparacoes!

Comparacao de Performance

Lista	Busca Linear	Busca Binaria
100 elementos	ate 100 passos	ate 7 passos
1.000 elementos	ate 1.000 passos	ate 10 passos
1.000.000 elementos	ate 1.000.000 passos	ate 20 passos
1.000.000.000 elementos	ate 1 bilhao passos	ate 30 passos

Implementacao Iterativa

A versao iterativa e a mais usada na pratica por ser mais eficiente em memoria (sem overhead de recursao):

def busca_binaria(lista, alvo):
    """
    Busca binaria iterativa.
    Retorna o indice do elemento ou -1 se nao encontrado.
    """
    esquerda = 0
    direita = len(lista) - 1

    while esquerda <= direita:
        meio = (esquerda + direita) // 2
        valor_meio = lista[meio]

        if valor_meio == alvo:
            return meio
        elif valor_meio < alvo:
            # Alvo esta na metade direita
            esquerda = meio + 1
        else:
            # Alvo esta na metade esquerda
            direita = meio - 1

    return -1  # Nao encontrado

# Uso
numeros = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

print(busca_binaria(numeros, 23))   # 5
print(busca_binaria(numeros, 50))   # -1
print(busca_binaria(numeros, 2))    # 0
print(busca_binaria(numeros, 91))   # 9

Como Funciona Passo a Passo

Buscando o valor 23 em [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]:

Passo	Esquerda	Direita	Meio	Valor	Acao
1	0	9	4	16	16 < 23 → esquerda = 5
2	5	9	7	56	56 > 23 → direita = 6
3	5	6	5	23	Encontrado no indice 5

Apenas 3 passos para encontrar o elemento em uma lista de 10 elementos.

Implementacao Recursiva

A versao recursiva e mais elegante e facil de entender, porem usa mais memoria por causa da pilha de chamadas:

def busca_binaria_recursiva(lista, alvo, esquerda=0, direita=None):
    """
    Busca binaria recursiva.
    Retorna o indice do elemento ou -1 se nao encontrado.
    """
    if direita is None:
        direita = len(lista) - 1

    # Caso base: elemento nao encontrado
    if esquerda > direita:
        return -1

    meio = (esquerda + direita) // 2

    if lista[meio] == alvo:
        return meio
    elif lista[meio] < alvo:
        return busca_binaria_recursiva(lista, alvo, meio + 1, direita)
    else:
        return busca_binaria_recursiva(lista, alvo, esquerda, meio - 1)

# Uso
numeros = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(busca_binaria_recursiva(numeros, 23))  # 5

Atencao: Python tem um limite de recursao padrao de 1000 (configuravel com sys.setrecursionlimit()). Para listas muito grandes, prefira a versao iterativa. Para entender melhor recursao e tratamento de erros, consulte nosso guia.

Modulo bisect: Busca Binaria Profissional

O modulo bisect da biblioteca padrao oferece busca binaria otimizada, implementada em C:

import bisect

# Lista ordenada
numeros = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

# bisect_left: ponto de insercao a esquerda
pos = bisect.bisect_left(numeros, 23)
print(pos)  # 5 (indice onde 23 esta)

# Verificar se o elemento existe
def buscar(lista, alvo):
    pos = bisect.bisect_left(lista, alvo)
    if pos < len(lista) and lista[pos] == alvo:
        return pos
    return -1

print(buscar(numeros, 23))   # 5
print(buscar(numeros, 50))   # -1

bisect_left vs bisect_right

import bisect

# Lista com duplicatas
notas = [5.0, 6.0, 7.0, 7.0, 7.0, 8.0, 9.0]

# bisect_left: insere ANTES dos iguais
print(bisect.bisect_left(notas, 7.0))   # 2

# bisect_right: insere DEPOIS dos iguais
print(bisect.bisect_right(notas, 7.0))  # 5

# Util para encontrar o intervalo de elementos iguais
esquerda = bisect.bisect_left(notas, 7.0)
direita = bisect.bisect_right(notas, 7.0)
print(f"Notas 7.0 estao nos indices {esquerda} a {direita - 1}")
# "Notas 7.0 estao nos indices 2 a 4"

insort: Inserir Mantendo a Ordem

import bisect

# Manter lista ordenada durante insercoes
placar = [72, 85, 91, 95]

bisect.insort(placar, 88)
print(placar)  # [72, 85, 88, 91, 95]

bisect.insort(placar, 65)
print(placar)  # [65, 72, 85, 88, 91, 95]

insort() e equivalente a lista.insert(bisect.bisect_right(lista, x), x), mas otimizado.

Aplicacoes Praticas

Classificacao por Faixa

import bisect

def classificar_nota(nota):
    faixas = [6.0, 7.0, 8.0, 9.0]
    conceitos = ["F", "D", "C", "B", "A"]
    indice = bisect.bisect(faixas, nota)
    return conceitos[indice]

print(classificar_nota(5.5))   # "F"
print(classificar_nota(6.0))   # "D"
print(classificar_nota(7.5))   # "C"
print(classificar_nota(9.5))   # "A"

Buscar o Valor Mais Proximo

import bisect

def valor_mais_proximo(lista_ordenada, alvo):
    pos = bisect.bisect_left(lista_ordenada, alvo)

    if pos == 0:
        return lista_ordenada[0]
    if pos == len(lista_ordenada):
        return lista_ordenada[-1]

    antes = lista_ordenada[pos - 1]
    depois = lista_ordenada[pos]

    return antes if (alvo - antes) <= (depois - alvo) else depois

precos = [9.90, 19.90, 29.90, 49.90, 99.90]
print(valor_mais_proximo(precos, 35.00))  # 29.90
print(valor_mais_proximo(precos, 45.00))  # 49.90

Busca Binaria em Strings

import bisect

# Dicionario de palavras ordenado
palavras = ["abacaxi", "banana", "cereja", "damasco", "figo", "goiaba"]

def buscar_palavra(dicionario, palavra):
    pos = bisect.bisect_left(dicionario, palavra)
    if pos < len(dicionario) and dicionario[pos] == palavra:
        return f"'{palavra}' encontrada no indice {pos}"
    return f"'{palavra}' nao encontrada"

print(buscar_palavra(palavras, "cereja"))    # Encontrada
print(buscar_palavra(palavras, "manga"))     # Nao encontrada

Busca Binaria em Entrevistas Tecnicas

Busca binaria e um dos temas mais cobrados em entrevistas tecnicas Python. Problemas classicos incluem:

Encontrar o Primeiro/Ultimo Indice

import bisect

def primeiro_indice(lista, alvo):
    """Encontra o primeiro indice de um valor em lista com duplicatas."""
    pos = bisect.bisect_left(lista, alvo)
    if pos < len(lista) and lista[pos] == alvo:
        return pos
    return -1

def ultimo_indice(lista, alvo):
    """Encontra o ultimo indice de um valor em lista com duplicatas."""
    pos = bisect.bisect_right(lista, alvo) - 1
    if pos >= 0 and lista[pos] == alvo:
        return pos
    return -1

numeros = [1, 2, 2, 2, 3, 4, 5]
print(primeiro_indice(numeros, 2))  # 1
print(ultimo_indice(numeros, 2))    # 3

Raiz Quadrada Inteira

def raiz_quadrada_inteira(n):
    """Encontra o maior inteiro x onde x*x <= n."""
    esquerda, direita = 0, n

    while esquerda <= direita:
        meio = (esquerda + direita) // 2
        quadrado = meio * meio

        if quadrado == n:
            return meio
        elif quadrado < n:
            esquerda = meio + 1
        else:
            direita = meio - 1

    return direita  # Maior inteiro cujo quadrado <= n

print(raiz_quadrada_inteira(16))   # 4
print(raiz_quadrada_inteira(20))   # 4 (4^2=16 <= 20, 5^2=25 > 20)

Complexidade e Analise

Aspecto	Busca Linear	Busca Binaria
Complexidade	O(n)	O(log n)
Pre-requisito	Nenhum	Lista ordenada
Espaco extra	O(1)	O(1) iterativa, O(log n) recursiva
Melhor para	Listas pequenas, nao ordenadas	Listas grandes, ordenadas
Implementacao	Simples	Moderada

Quando Nao Usar Busca Binaria

Dados nao ordenados: O custo de ordenar O(n log n) pode nao compensar
Poucas buscas: Se busca apenas uma vez, busca linear pode ser suficiente
Dados em dicionarios: Use dict para busca O(1) por chave
Dados dinamicos: Se insere/remove frequentemente, considere arvores balanceadas

Conclusao

Busca binaria e um algoritmo fundamental que todo desenvolvedor Python deve dominar. Na pratica, use o modulo bisect para codigo de producao e implemente manualmente para entrevistas e aprendizado.

Continue explorando algoritmos e estruturas de dados: listas, dicionarios, ordenacao e pilhas e filas.

Para mais desafios de algoritmos em Python, prepare-se com nosso guia de entrevistas Python e confira as vagas Python disponveis no mercado.

Algoritmos sao universais — veja como implementar em outras linguagens: Go, Rust e Kotlin.