Busca linear (linear search) em Python
Nesta lição, você vai implementar a busca linear para encontrar a posição de um valor em uma lista.
O que é busca linear?
O problema
Às vezes os dados não estão ordenados, ou você só vai buscar uma vez: uma lista curta de nomes, os pedidos de hoje, o primeiro erro em um log. Você precisa da busca mais simples, que sempre funciona.
Pense assim
A busca linear é como procurar as chaves nos bolsos de uma fileira de casacos. Você olha o primeiro bolso, depois o próximo, um por um, e para assim que encontra. Se chegar ao último bolso, as chaves não estão ali.
for index, value in enumerate(values):🧥 Olhe cada bolso em ordemif value == target:🔑 As chaves estão aqui?return index✅ Achou: pare de procurarreturn -1❌ Olhou todos os bolsos: não encontradoA busca linear verifica os itens de uma coleção um após o outro até encontrar o alvo. Ela leva até O(n) passos, mas não precisa de ordenação.
A busca linear verifica cada item desde o início até encontrar o alvo ou chegar ao fim. Os dados não precisam estar ordenados.
Como o algoritmo funciona
- Começar no índice 0.
- Comparar o item atual com o alvo.
- Retornar o índice quando forem iguais; caso contrário, continuar.
- Retornar -1 após o último item quando não houver correspondência.
Quando usar?
- Coleções pequenas ou não ordenadas.
- Buscar uma única vez, quando ordenar antes custaria mais.
- Encontrar o primeiro item que satisfaz uma condição, não só um valor exato.
Quando não é preciso
- Muitas buscas nos mesmos dados grandes: ordene uma vez e use busca binária, ou crie um set ou dicionário.
- Só verificar se um valor está presente:
target in valuesfaz o mesmo com menos código.
Visualizador de Busca linear (linear search) em Python
O(n)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))
Resultado da execução
3
Explicação do código
A função enumerate() fornece a posição e o valor de cada elemento. Assim que encontra o valor procurado, a função retorna essa posição, que aqui é 3. Se percorrer a lista toda sem encontrá-lo, retorna -1. No pior caso, o algoritmo verifica todos os elementos, então a complexidade é O(n).
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.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Devolver -1 dentro do laço
A busca desiste depois do primeiro item que não corresponde.
for index, value in enumerate(values):
if value == target:
return index
return -1
for index, value in enumerate(values):
if value == target:
return index
return -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.
- First Negative Index Find where the first negative number appears. Fácil
- Mínimo do Array Encontre o menor valor em uma lista. Fácil