Durante nossas aulas de algoritmos, exploramos diferentes formas de buscar elementos em uma lista. Hoje, vamos nos aprofundar em dois algoritmos fundamentais: a busca linear e a busca binária. Esses algoritmos são a base para entendermos conceitos de complexidade e eficiência computacional, além de serem amplamente utilizados no dia a dia da programação.
1. Busca Linear
A busca linear, também conhecida como busca sequencial, percorre cada elemento da lista até encontrar o valor desejado. É o método mais simples e não requer que os dados estejam ordenados. O algoritmo compara cada elemento com o alvo e retorna a posição quando encontra; se chegar ao final da lista sem sucesso, retorna um valor indicando falha (geralmente -1).
Vantagens: simplicidade de implementação, funciona em qualquer lista (ordenada ou não), não exige estrutura auxiliar. Desvantagens: para listas grandes o desempenho é baixo, pois a complexidade é O(n) no pior caso e O(n/2) em média.
def busca_linear(lista, alvo):
for i in range(len(lista)):
if lista[i] == alvo:
return i
return -1
Exemplo: Se temos lista = [10, 23, 45, 70, 11, 15] e buscamos 70, a função retornará 3 (índice). Se buscarmos 99, retornará -1.
2. Busca Binária
A busca binária é um algoritmo muito mais eficiente, porém exige que a lista esteja ordenada (em ordem crescente, para o caso padrão). Ela funciona dividindo repetidamente o intervalo de busca pela metade, comparando o elemento do meio com o alvo e descartando a metade onde o valor não pode estar.
Pré-requisito: lista ordenada. Complexidade: O(log n) no pior caso, o que representa uma enorme economia para listas grandes.
def busca_binaria(lista, alvo):
esquerda, direita = 0, 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>
Passo a passo: Suponha lista = [1, 3, 5, 7, 9, 11, 13] e alvo = 7.
- Início: esquerda = 0, direita = 6, meio = 3 → lista[3] = 7 → encontrado! Retorna 3.
- Se o alvo fosse 8: meio = 3 → 7 < 8 → esquerda = 4; novo meio = (4+6)//2 = 5 → lista[5] = 11 > 8 → direita = 4; agora esquerda = 4, direita = 4, meio = 4 → lista[4] = 9 > 8 → direita = 3; esquerda (4) > direita (3) → retorna -1.
3. Comparação entre Busca Linear e Binária
| Critério | Busca Linear | Busca Binária |
|---|---|---|
| Pré‑requisito | Nenhum | Lista ordenada |
| Complexidade (pior caso) | O(n) | O(log n) |
| Complexidade (melhor caso) | O(1) – primeiro elemento | O(1) – elemento do meio |
| Espaço extra | O(1) – iterativo | O(1) – iterativo; O(log n) – recursivo (pilha) |
| Quando usar | Listas pequenas, não ordenadas, ou busca única | Listas grandes e ordenadas, múltiplas buscas |
Na prática, para listas com dezenas de milhares de elementos, a busca binária pode ser centenas de vezes mais rápida. Porém, a ordenação prévia tem custo O(n log n) – se a lista for alterada com frequência, a busca linear pode ser mais conveniente.
4. Implementação Recursiva da Busca Binária
def busca_binaria_recursiva(lista, alvo, esquerda, direita):
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)>A versão recursiva tem a mesma complexidade, mas consome espaço na pilha de chamadas proporcional a O(log n). Para listas muito grandes, a versão iterativa é preferível.
5. Exercícios
- Implemente a busca binária recursiva e compare o número de chamadas com o iterativo.
- Dada uma lista de 1 milhão de números ordenados, quantas comparações a busca binária faz no pior caso? (Resposta: cerca de 20).
- Modifique a busca linear para retornar todas as posições onde o elemento aparece (lista com elementos repetidos).
- Pesquise sobre a busca ternária: em que situações ela pode ser útil?
Perguntas Frequentes
Qual a diferença principal entre busca linear e binária?
A busca linear percorre todos os elementos sequencialmente, enquanto a binária divide o espaço de busca pela metade a cada passo. A binária exige ordenação prévia, mas é muito mais rápida para grandes conjuntos de dados.
A busca binária funciona em listas não ordenadas?
Não. Se a lista não estiver ordenada, a premissa de descartar metades não é válida, e o algoritmo pode retornar uma posição incorreta ou não encontrar o elemento mesmo que ele exista. Nesse caso, a busca linear é a escolha correta.
Quando devo usar a busca binária mesmo com o custo da ordenação?
Se você precisa realizar muitas consultas em uma mesma base de dados que é raramente modificada, vale a pena ordená‑la uma vez (O(n log n)) e depois usar busca binária (O(log n) por consulta). O ganho acumulado supera o custo inicial. Para consultas esporádicas, a busca linear é mais simples e suficiente.