Pesquisa linear em Python: Um guia para iniciantes com exemplos

Quando se trata de algoritmos de pesquisa, a pesquisa linear é uma das mais simples. Se você já procurou em uma lista de itens, um por um, até encontrar o que estava procurando, então você já fez uma busca linear!

Além de ser fácil de entender, a pesquisa linear é útil porque funciona com dados não classificados, ao contrário de outros algoritmos de pesquisa. Essa versatilidade o torna uma opção útil em cenários em que a classificação de dados não é possível. Usarei o Python neste tutorial, portanto, se, antes de começarmos, você quiser se atualizar sobre o Python, confira a trilha de habilidades de programação em Python.

O que é pesquisa linear?

A pesquisa linear é um algoritmo que localiza um valor específico em uma lista, verificando cada elemento um a um. Ele começa no primeiro item, compara-o com o alvo e continua a percorrer a lista até encontrar o alvo ou chegar ao final da lista. É um algoritmo simples e intuitivo.

A pesquisa linear não precisa que os dados sejam classificados para funcionar, portanto, ela é usada principalmente em conjuntos de dados não classificados. Isso o torna útil para situações em que a classificação não é prática ou em que você está trabalhando com dados em sua forma bruta. No entanto, esse benefício tem um custo: ele não é tão eficiente quanto outros algoritmos que exigem dados pré-selecionados.

A pesquisa linear é ideal em situações em que você está trabalhando com conjuntos de dados relativamente pequenos ou quando a classificação dos dados não é viável. O diagrama abaixo fornece uma explicação simplificada.

Escolhendo a pesquisa linear

Vamos dar uma olhada nas vantagens e também em uma desvantagem distinta: 

Por que escolher o Linear Search?

Na minha opinião, a pesquisa linear tem três benefícios distintos:

Quando a simplicidade é fundamental

Uma das maiores vantagens da pesquisa linear é sua simplicidade. O algoritmo é fácil de entender e implementar. Você não precisa se preocupar com classificações complexas ou com a divisão dos dados. Basta começar no início da lista e verificar cada elemento até encontrar o que você está procurando.

Quando você não tem tempo para classificar

Diferentemente de outros algoritmos de pesquisa, como a pesquisa binária, a pesquisa linear não exige que o conjunto de dados seja classificado. Isso o torna perfeito para quando você precisa de uma maneira rápida de encontrar algo.

Quando você precisa de versatilidade

Outra vantagem da pesquisa linear é que ela é versátil. Ele funciona não apenas com matrizes, mas também com outras estruturas de dados do Python, como listas vinculadas. Desde que você possa acessar sequencialmente os elementos, a pesquisa linear pode fazer o trabalho. Ele é flexível o suficiente para lidar com diferentes tipos de dados, de números a cadeias de caracteres e até mesmo objetos.

Por que pensar duas vezes sobre a pesquisa linear?

Há uma questão a ser considerada:

Quando a eficiência é importante

A principal desvantagem da pesquisa linear é sua ineficiência, especialmente com grandes conjuntos de dados. Sua complexidade de tempo é O(n), o que significa que, na pior das hipóteses, você pode ter que verificar cada elemento da lista! Isso pode realmente tornar as coisas mais lentas se você estiver trabalhando com milhares ou milhões de entradas. No entanto, para conjuntos de dados pequenos, essa ineficiência pode ser insignificante.

Implementação de um algoritmo de pesquisa linear em Python

Em Python, há duas maneiras comuns de escrever uma pesquisa linear: o método iterativo e o método recursivo. Para demonstrar esses dois métodos, vamos primeiro criar um conjunto de dados simples de 100 números sem duplicatas.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]

Método iterativo

A abordagem iterativa é provavelmente a maneira mais fácil de entender a pesquisa linear. Você percorre a lista, verificando cada elemento até encontrar o alvo ou chegar ao final.

Primeiro, criaremos nossa função:

1. Faremos um loop em cada elemento da lista arr.

2. Vamos comparar cada elemento com o alvo.

3. Se encontrarmos uma correspondência, retornaremos o índice em que o alvo foi encontrado.

4. Se terminarmos o loop sem encontrar o alvo, retornaremos 1 para indicar que o elemento não está presente.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not found

Em seguida, executaremos nossa função em nosso conjunto de dados e imprimiremos o resultado:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")

Ao executar esse código, você encontra o valor-alvo no 23º elemento.

Método recursivo

O método recursivo usa uma função que chama a si mesma para pesquisar na lista. Cada chamada recursiva processa um elemento de cada vez e, em seguida, passa para o próximo elemento. Isso continua até que o alvo seja encontrado ou o final da lista seja alcançado.

Vamos criar nossa função recursiva:

1. Começaremos verificando o primeiro elemento (no índice 0).
2. Se o destino corresponder, retornaremos o índice.
3. Se o destino não corresponder, chamaremos a mesma função recursivamente, mas incrementaremos o índice em 1 para verificar o próximo elemento.
4. A recursão continua até encontrarmos o alvo ou chegarmos ao final da lista.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next element

Podemos usar o mesmo código acima para executar essa função e ela retornará o mesmo valor de índice para o nosso alvo: 23.

Lembre-se de que essa abordagem usa mais memória porque cada chamada recursiva adiciona uma nova camada à pilha de chamadas. Confira Understanding Recursive Functions in Python (Entendendo as funções recursivas em Python ) para que você possa dar uma olhada mais de perto na recursão.

Complexidade de tempo e espaço

Uma maneira de avaliar a eficiência de um algoritmo é observar sua complexidade de tempo e espaço. Confira o tutorial Analisando a complexidade do código por meio do Python para ver as diferentes maneiras de medir a complexidade de um algoritmo.

Complexidade de tempo

A complexidade de tempo de um algoritmo refere-se a como o tempo necessário para concluí-lo aumenta à medida que o tamanho da entrada cresce. A complexidade de tempo da pesquisa linear é O(n), em que n é o número de elementos da lista. Isso significa que, na pior das hipóteses, o algoritmo pode precisar verificar cada elemento antes de encontrar o alvo (ou determinar que o alvo não está na lista). Isso é bastante ineficiente, especialmente para grandes conjuntos de dados. É por isso que a pesquisa linear funciona melhor quando temos conjuntos de dados menores e não classificados que só precisam ser pesquisados uma vez.

Complexidade espacial

A complexidade espacial de um algoritmo é uma medida da quantidade de memória necessária à medida que o tamanho da entrada aumenta. A complexidade de espaço do algoritmo de pesquisa linear depende do método que usamos. Para o método iterativo, a complexidade espacial é O(1), o que significa que o algoritmo requer uma quantidade constante de memória, independentemente do tamanho da lista de entrada. Isso ocorre porque a versão iterativa não requer nenhuma memória adicional, além da lista de entrada e de algumas variáveis para manter o controle do índice atual.

Para o método recursivo, a complexidade espacial é O(n), o que significa que a memória necessária cresce linearmente com o tamanho da lista de entrada. Isso se deve às chamadas de função recursivas, que adicionam camadas à pilha de chamadas para cada elemento da lista. Uma lista maior requer mais memória para armazenar essas chamadas, o que torna a abordagem recursiva menos eficiente em termos de espaço.

Aplicações reais de pesquisa linear

Embora a pesquisa linear possa não ser o algoritmo mais eficiente para grandes conjuntos de dados, ela tem usos práticos em muitos cenários. Vamos dar uma olhada em algumas situações em que a pesquisa linear é a melhor ferramenta para o trabalho.

Conjuntos de dados pequenos em que a classificação não é prática

A pesquisa linear costuma ser a minha opção quando lido com pequenos conjuntos de dados que não valem o tempo ou os recursos para serem classificados. Nesses casos, a simplicidade da pesquisa linear pode ser mais eficiente do que a sobrecarga de classificação dos dados para algoritmos de pesquisa mais complexos.

Encontrar a primeira ocorrência de um alvo

Outro caso de uso comum da pesquisa linear é quando você precisa encontrar a primeira ocorrência de um valor de destino. Como a pesquisa linear percorre a lista um elemento de cada vez, ela naturalmente encontra a primeira instância do destino e retorna sua posição. Isso pode ser especialmente útil em casos como pesquisar em uma cadeia de caracteres a primeira aparição de um caractere.

Quando é necessária uma configuração mínima

Às vezes, a simplicidade da pesquisa linear faz dela a melhor opção. Por exemplo, se você estiver pesquisando rapidamente dados que não espera reutilizar ou se precisar de uma resposta rápida, a configuração mínima da pesquisa linear pode economizar seu tempo.

Pesquisa linear vs. pesquisa de dados Outros algoritmos de pesquisa

A pesquisa linear é apenas um dos muitos algoritmos de pesquisa existentes. Vamos dar uma olhada em dois outros algoritmos de pesquisa comuns: pesquisa binária e pesquisa de hash.

Pesquisa linear vs. pesquisa binária

A pesquisa binária é um algoritmo que encontra a posição de um valor-alvo em uma matriz classificada, dividindo repetidamente o intervalo de pesquisa pela metade. Ele tem uma complexidade de tempo de O(log n), o que o torna muito mais eficiente do que a pesquisa linear. No entanto, ele só funciona em dados classificados. Quando o conjunto de dados é classificado, a pesquisa binária é quase sempre a melhor opção, pois corta o espaço de pesquisa pela metade a cada etapa, reduzindo drasticamente o número de comparações necessárias para encontrar o alvo.

A pesquisa linear pode ser mais apropriada em situações em que os dados não estão classificados, já que a pesquisa linear funciona em qualquer conjunto de dados, classificados ou não. No entanto, com uma complexidade de tempo de O(n), a pesquisa linear é muito menos eficiente em conjuntos de dados classificados.

Pesquisa linear vs. pesquisa de hash

A pesquisa de hash é um método que usa uma tabela de hash para localizar rapidamente um elemento. Com uma complexidade de tempo de O(1), ele é significativamente mais rápido do que a pesquisa linear ou binária. No entanto, essa velocidade tem um custo: você precisa primeiro criar uma tabela de hash, o que requer tempo e memória adicional. As pesquisas de hash funcionam melhor quando você precisa pesquisar em grandes conjuntos de dados várias vezes para que a configuração inicial seja compensada com o tempo.

Por outro lado, a pesquisa linear não requer configuração, o que a torna uma opção mais simples. É a melhor opção quando você precisa pesquisar apenas uma ou poucas vezes, onde o tempo extra para configurar uma tabela de hash não é justificável. A pesquisa linear também pode ser mais eficiente em termos de espaço porque você não precisa armazenar uma tabela de hash para usar o algoritmo.

Armadilhas comuns e como evitá-las

Embora a pesquisa linear seja um algoritmo simples, há alguns erros comuns aos quais você deve estar atento.

Erros de iteração de um para um

Um dos erros mais frequentes na implementação de uma pesquisa linear é o erro "off-by-one". Isso é causado pelo fato de você iniciar ou parar a iteração no índice errado. É importante lembrar que as listas Python são indexadas a zero, o que significa que o primeiro elemento tem um índice 0. Se você se esquecer disso, poderá pular acidentalmente o primeiro elemento ou iterar uma etapa a mais, o que levará a resultados incorretos ou erros.

Não entender o índice retornado

Outra armadilha comum é não entender o que a função retorna quando o alvo não é encontrado na lista. Por convenção, muitos algoritmos de busca (inclusive a busca linear) retornam -1 para indicar que o alvo não está presente. No entanto, alguns iniciantes podem presumir que ele retorna None, False, ou algum outro valor, o que causa confusão ao interpretar os resultados.

Quando não usar a pesquisa linear

Como mencionamos anteriormente, a pesquisa linear rapidamente se torna ineficiente para conjuntos de dados maiores. Por esse motivo, é melhor reservá-lo para conjuntos de dados pequenos e não classificados ou para pesquisas rápidas e únicas.

Conclusão

Como um dos métodos de pesquisa mais simples, a pesquisa linear verifica cada elemento de uma lista sequencialmente, o que facilita a compreensão e a implementação. A pesquisa linear é uma opção confiável para pesquisas rápidas e únicas em conjuntos de dados pequenos, especialmente quando os dados não estão classificados.

Se você estiver interessado em algoritmos de pesquisa, confira meus outros artigos desta série: Pesquisa binária em Python, Pesquisa em profundidade em Python e Pesquisa em profundidade em Python. Você também pode estar interessado em AVL Tree: Complete Guide With Python Implementation e Introduction to Network Analysis in Python como tópicos mais avançados.