--- title: "Busca Binaria em Python: Como Implementar e Quando Usar" url: "https://python.dev.br/algoritmos/busca-binaria-python/" markdown_url: "https://python.dev.br/algoritmos/busca-binaria-python.MD" description: "Aprenda busca binaria em Python: implementacao iterativa e recursiva, modulo bisect, complexidade O(log n) e aplicacoes praticas. Guia completo com exemplos." date: "2026-04-27" author: "Equipe Python Brasil" --- # Busca Binaria em Python: Como Implementar e Quando Usar Aprenda busca binaria em Python: implementacao iterativa e recursiva, modulo bisect, complexidade O(log n) e aplicacoes praticas. Guia completo com exemplos. ## 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](/algoritmos/listas-python/) e entender [algoritmos de ordenacao](/algoritmos/ordenacao-python/), 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 ```python 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 ```python 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): ```python 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: ```python 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](/blog/tratamento-de-erros-python/), consulte nosso guia. --- ## Modulo bisect: Busca Binaria Profissional O modulo `bisect` da biblioteca padrao oferece busca binaria otimizada, implementada em C: ```python 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 ```python 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 ```python 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 ```python 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 ```python 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 ```python 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](/carreira/entrevistas-python/). Problemas classicos incluem: ### Encontrar o Primeiro/Ultimo Indice ```python 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 ```python 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](/algoritmos/dicionarios-python/)**: 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](/algoritmos/listas-python/), [dicionarios](/algoritmos/dicionarios-python/), [ordenacao](/algoritmos/ordenacao-python/) e [pilhas e filas](/algoritmos/pilhas-filas-python/). Para mais desafios de algoritmos em Python, prepare-se com nosso guia de [entrevistas Python](/carreira/entrevistas-python/) e confira as [vagas Python](/vagas/) disponveis no mercado.

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