Pesquisa Linear em Python
A pesquisa é um método para determinar se um elemento específico está contido na lista fornecida ou não. Pesquisa Linear e Pesquisa Binária são duas formas diferentes de pesquisa. Ambos os métodos são freqüentemente usados ​​para encontrar um elemento específico na lista fornecida.
O que é pesquisa linear em Python?
Para completar nossas tarefas com eficiência, empregamos certos algoritmos para procurar um elemento em uma determinada estrutura de dados. Algoritmos de pesquisa é outro nome para tais algoritmos. Algoritmos de pesquisa linear, algoritmos de pesquisa binária, algoritmos de pesquisa de interpolação, algoritmos de pesquisa de salto, etc. são alguns exemplos de algoritmos de pesquisa usados ​​com frequência.
A pesquisa linear em Python é uma maneira de encontrar itens em uma lista. Uma maneira sequencial é usada para encontrar o elemento solicitado. Cada elemento é verificado quanto ao valor que buscamos. Se ambos forem iguais, o elemento é encontrado e o processo retorna a posição do índice desse elemento.
Vamos ter uma ideia geral de como funciona a pesquisa linear em Python:
- Comece com o primeiro elemento da lista e percorra a lista verificando a chave de cada elemento.
- A posição do índice do elemento é retornada se um valor de elemento for igual ao de uma chave.
- O valor de retorno é nulo se o elemento não for encontrado.
Como realizar pesquisa linear em Python?
Agora vamos entender o bom funcionamento da pesquisa linear em python com um exemplo.
Suponha que seja fornecida uma lista de elementos e digamos que queremos procurar o valor 29 nessa lista. A lista de elementos é fornecida abaixo.
A explicação passo a passo do exemplo é fornecida abaixo.
Passo 1: Levamos em consideração o primeiro valor, que é 20 da lista, e comparamos com o nosso valor de pesquisa, que é 29. Passamos para o valor seguinte da lista porque não é igual.
Passo 2: A seguir, levamos em consideração o segundo elemento que é 64, e o comparamos com nosso valor requerido de 0. Prosseguimos para o elemento seguinte mais uma vez porque ele não é igual.
Etapa 3: Agora temos 6 como o próximo elemento da lista. Quando comparamos os dois elementos, vemos que 6 não é equivalente a 29. Passamos agora para o próximo elemento.
Etapa 4: agora temos 29 como nosso próximo elemento. Portanto, este 29 é comparado ao nosso 29 necessário e identificamos o elemento que procurávamos na lista, pois 29 é equivalente a 29. O valor do índice do elemento é 3, agora esse valor do índice pode ser retornado para uso em cálculos adicionais após imprimirmos uma mensagem indicando que o elemento foi localizado no índice 3.
Este é um processo iterativo que você pode ver, portanto esta iteração continuará até que o elemento desejado seja identificado ou chegue ao final da lista. Quando chega ao final da lista, mas não há nenhum elemento correspondente, pode mostrar uma mensagem informando ao usuário que tal item não está presente na lista fornecida. Portanto, este é um algoritmo para pesquisa linear em Python, que você deve ter achado bastante simples.
Casos de uso de pesquisa linear
- Pode-se usar a pesquisa linear quando o tamanho do array não for muito grande ou for constante, é mais fácil/rápido de implementar, economizando tempo de desenvolvimento.
- Este alogritmo é fácil de entender e aplicar, portanto pode ser usado pelos desenvolvedores para pesquisar um elemento em um array de tamanho pequeno.
Algoritmo de pesquisa linear Python
Atualmente temos uma ideia básica de como funciona a pesquisa linear em Python. Para um melhor entendimento, vejamos o algoritmo seguido do código:
- Crie a função de pesquisa linear().
- Declare a matriz, o comprimento da matriz e o valor a ser encontrado como três parâmetros.
- Inicialize o loop for.
- Compare o valor da chave com cada elemento conforme você itera.
- Retorna o índice se o elemento estiver presente.
- caso contrário, o elemento de retorno está ausente.
Programa Python para pesquisa linear
Agora vamos mergulhar na parte de programação desta pesquisa linear em Python.
Um exemplo fornecido a seguir é para pesquisar o índice 6 na matriz fornecida, se estiver presente.
Agora, como você pode ver no exemplo acima, precisamos que 6 seja pesquisado no array fornecido, esteja ele presente lá ou não. Assim a função começa a procurar o 6 do 1º elemento da lista e finalmente descobre o elemento 6 no índice 2, então a função retornará a afirmação de que "O elemento está no índice 2".
Um exemplo fornecido a seguir é para pesquisar o índice 9 na matriz fornecida, se estiver presente.
Agora, como você pode ver no exemplo acima, precisamos que 9 seja pesquisado no array fornecido, esteja ele presente lá ou não. Assim a função começa a procurar o 9 no primeiro elemento da lista e após percorrer a lista até o último elemento o 9 não foi encontrado. Portanto, a função retornará a instrução Element Not Found.
Um exemplo fornecido a seguir é para pesquisar o índice 2 na matriz fornecida, se estiver presente.
Agora, como você pode ver no exemplo acima, precisamos que 2 seja pesquisado no array fornecido, esteja ele presente lá ou não. Assim a função começa a procurar 2 no 1º elemento da lista e finalmente após percorrer toda a lista foi encontrado no último índice que é 4, então a função retornará a afirmação de que “O elemento está no índice 4”.
P. Qual é a complexidade de tempo para realizar uma pesquisa linear em Python, em um array?
A. A complexidade de tempo do algoritmo de pesquisa linear é:
- Para o caso base é
- Para o caso médio é
- Na pior das hipóteses é
Como a técnica de busca linear verifica cada elemento para descobrir o número desejado, ela é adequada para listas menores (menos de 100). Se houver 10.000 elementos na lista e o elemento obrigatório estiver no final, demorará muito para compará-lo com cada um. A técnica de pesquisa binária pode ser usada para obter resultados rapidamente.
P. Qual é a complexidade do espaço para realizar uma pesquisa linear em Python, em um array?
A. Como nenhum espaço extra ou auxiliar é usado durante todo o processo de busca da busca linear, a complexidade do espaço para realizar a busca linear será.
- Pesquisa sequencial é outro nome dado à pesquisa linear.
- A pesquisa linear em Python leva muito mais tempo em comparação com a pesquisa binária se um elemento estiver presente no último índice.
- A pesquisa linear em Python é adequada para pesquisar em pequenos arrays.