Busca linear e busca binária
Como encontrar um elemento em uma lista? A busca linear olha um por um — simples, mas lenta: O(n). A busca binária divide a lista ao meio a cada passo — exige lista ordenada, mas é drasticamente mais rápida: O(log n). Para 1 bilhão de elementos, a diferença é entre 1 bilhão e 30 comparações.
Achar um nome na lista telefônica
A lista telefônica está ordenada por nome. Se você quer achar "Silva", não começa do "A" e vai letra a letra (busca linear). Você abre no meio, vê "Moreira", e sabe que "Silva" está depois. Abre na metade desse restante, e assim por diante. Isso é busca binária: cada passo elimina metade das possibilidades.
Mas se a lista não está ordenada — como uma lista de compras aleatória — não tem como fazer isso. Você precisa olhar item por item. É a busca linear: necessária quando não há ordem, rápida o suficiente para listas pequenas.
Veja cada passo de cada algoritmo
Escolha o algoritmo, selecione o valor a buscar, e avance passo a passo. Observe quantas comparações cada um precisa.
Busca linear — O(n)
# Busca linear — O(n) — funciona em qualquer lista def busca_linear(lista, alvo): for i, v in enumerate(lista): if v == alvo: return i # encontrado no índice i return -1 # não encontrado # Melhor caso: O(1) — achou na primeira posição # Pior caso: O(n) — elemento ausente ou na última posição # Requisito: NENHUM — funciona em listas não ordenadas
Busca binária — O(log n)
# Busca binária — O(log n) — exige lista ORDENADA def busca_binaria(lista, alvo): l, r = 0, len(lista) - 1 while l <= r: m = (l + r) // 2 # índice do meio if lista[m] == alvo: return m # achou! elif lista[m] < alvo: l = m + 1 # alvo está à direita else: r = m - 1 # alvo está à esquerda return -1 # não encontrado # Para n = 1.000.000: máx 20 comparações (log₂(10⁶) ≈ 20) # Para n = 1.000.000.000: máx 30 comparações (log₂(10⁹) ≈ 30) # Python já tem bisect_left/bisect_right: import bisect pos = bisect.bisect_left(lista_ordenada, alvo) encontrado = pos < len(lista_ordenada) and lista_ordenada[pos] == alvo
Implementando e comparando
Mini projeto: implemente ambas as buscas em Python. Para cada n ∈ {100, 1.000, 10.000, 100.000}, gere uma lista ordenada e conte o número de comparações no pior caso (buscar um elemento que não existe). Construa uma tabela com os resultados. O que acontece com o ratio linear/binária conforme n cresce?
Projeto principal: implemente um sistema de autocomplete simples: dado um dicionário com 200.000 palavras (use /usr/share/dict/words no Linux/Mac), encontre todas as palavras que começam com um prefixo digitado. Compare: busca linear (percorre tudo) vs busca binária para achar a posição inicial + scan. Meça o tempo com timeit.
Desafio extra: implemente busca binária de forma recursiva. Explique por que a versão iterativa é preferida na prática (dica: overhead de chamada de função e stack overflow para n muito grande). Depois implemente busca ternária (divide em 3 partes) e compare o número de comparações com a binária — surpreenda-se com o resultado.
Teste sua intuição
Onde você encontra isso
git bisect — encontrando bugs em histórico
O comando git bisect usa busca binária no histórico de commits para achar qual commit introduziu um bug. Com 1.000 commits, você precisaria testar apenas ~10 versões. Você marca "bom" e "ruim" em cada passo, e o git automaticamente divide o histórico ao meio. É literalmente busca binária aplicada a controle de versão.
Índices B-tree em bancos de dados
Índices em PostgreSQL, MySQL, e SQLite são implementados como B-trees (árvores B) — uma generalização da busca binária para armazenamento em disco. Com bilhões de registros, uma query WHERE id = 12345 encontra o resultado em ~4-5 leituras de disco (altura da árvore ≈ log n), em vez de fazer full table scan. Cada "nó" da árvore corresponde a uma página de disco.
Game development — detecção de colisão
Em jogos com milhares de objetos, verificar colisão entre todos os pares é O(n²) — impossível em tempo real. A solução usa estruturas de busca espacial (como BSP trees, octrees ou BVH) que dividem o espaço recursivamente, como busca binária em 3D. Cada frame, apenas objetos em regiões próximas são verificados: O(n log n) em vez de O(n²).