Pesquisa Linear: Python, C++ Exemplo
Sarah Chen
O que é algoritmo de pesquisa?
Um algoritmo de busca é projetado para encontrar um elemento ou objeto em uma coleção de elementos ou objetos com uma determinada estrutura de dados. Por exemplo, pesquise a altura mínima em uma determinada lista de alturas ou pesquise a marca mais alta em uma lista ou matriz de números. Poucos algoritmos de pesquisa populares incluem “Pesquisa Linear”, “Pesquisa Binária”, “Pesquisa de Salto”, “Pesquisa Fibonacci”, etc.
O que é pesquisa linear?
A pesquisa linear é um dos algoritmos de pesquisa mais simples. A partir de uma determinada lista ou array, ele procura o elemento fornecido um por um. A Pesquisa Linear itera sobre toda a lista e verifica se algum elemento específico é igual ao elemento de pesquisa. Também é chamado de pesquisa sequencial.
O que a função de pesquisa linear faz?
Uma matriz de inteiros é dada como “Numbers”, e uma variável “item” contém o número inteiro a ser pesquisado.
Agora, o algoritmo de pesquisa linear pode fornecer a seguinte saída:
- “-1”; isso significa que o elemento fornecido não foi encontrado na matriz
- Qualquer número entre 0 e n-1; significa que o elemento de pesquisa foi encontrado e retorna o índice do elemento na matriz. Aqui, “n” representa o tamanho do array.
Como funciona a Pesquisa Linear?
Digamos que um array contendo números inteiros. A tarefa é encontrar um determinado número na matriz.
- Se o número estiver localizado no array, precisamos retornar o índice desse número.
- Se o número fornecido não for encontrado, ele retornará -1.
No fluxograma, “Dados” é o array de inteiros, “N” é o tamanho do array e o “item” é o número que queremos pesquisar no array.
Fluxograma para algoritmo de pesquisa linear:
Aqui estão as etapas do fluxograma:
Passo 1) Leia o item de pesquisa, “item”.
Passo 2) Inicie i=0 e índice=-1
Passo 3) Se eu
Passo 4) Se Data[i] for igual a “item”, vá para a etapa 5. Caso contrário, vá para a etapa 6.
Passo 5) Índice = i (como o item é encontrado no índice no i). Vá para a etapa 8.
Passo 6) eu = eu +1.
Passo 7) Vá para a etapa 3.
Passo 8) Parar.
Para simplificar, fornecemos um exemplo com uma matriz de inteiros. A pesquisa linear também é aplicável na string, em uma matriz de objetos ou em uma estrutura.
Pseudocódigo para algoritmo de pesquisa sequencial
function linearSearch: in →Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as negative index is not valid return -1
C++ Exemplo de código de pesquisa linear
#include < bits / stdc++.h >
using namespace std;
int linearSearch(int * arr, int item, int n) {
int idx = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == item) {
idx = i;
break;
}
}
return idx;
}
int main() {
int array[] = {
1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
};
int n = sizeof(array) / sizeof(arr[0]);
int item;
cout << "Enter a number to search: ";
cin >> item;
int idx = linearSearch(arr, item, n);
if (idx >= 0) {
cout << item << " is found at index " << idx << endl;
} else {
cout << "Could not find " << item << " in the array" << endl;
}
}
Saída:
Enter a number to search: -10 -10 is found at index 14
Python Exemplo de código de pesquisa linear
def linearSearch(data, item):
for i in range(len(data)):
if data[i] == item:
return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
print("{} is found at index {}".format(item, idx))
else :
print("{} was not found".format(item))
Saída:
Enter a number to search: -10 -10 is found at index 14
Análise de complexidade do algoritmo de pesquisa linear
Geralmente, complexidade de tempo significa a quantidade de tempo de CPU para executar uma determinada tarefa. No algoritmo de busca linear, a tarefa é encontrar a chave de busca a partir do elemento do array.
Três tipos de complexidades de tempo são:
- Worst Case Scenario
- Melhor cenário de caso
- Cenário Médio de Caso
Complexidade temporal da pesquisa linear no pior cenário:
Digamos que precisamos realizar uma pesquisa linear em um array com tamanho “n”. Podemos encontrar o item de pesquisa entre o índice 0 a n-1. Na pior das hipóteses, o algoritmo tentará combinar todos os elementos do array com o elemento de pesquisa.
Nesse caso, a complexidade do pior caso será O(n). Aqui, a notação “O”-big O significa a função de complexidade.
Complexidade temporal da pesquisa linear no cenário Melhor-Case:
Digamos que estamos procurando um elemento que reside na primeira posição do array. Neste cenário, o algoritmo de pesquisa linear não pesquisará todos os n elementos da matriz. Portanto a complexidade será O(1). Isso significa tempo constante.
Complexidade temporal da pesquisa linear no cenário médio:
Quando um elemento é encontrado no índice intermediário do array, então pode-se dizer que a complexidade média do caso para pesquisa linear é O(N), onde N significa o comprimento do array.
A complexidade espacial do algoritmo de busca linear
A complexidade do espaço para a busca linear é sempre O(N) porque não precisamos armazenar ou usar nenhum tipo de variável temporária na função de busca linear.
Como melhorar o algoritmo de pesquisa linear
A pesquisa pode ser feita diversas vezes durante o ciclo de vida do programa. Também é possível que estejamos executando o algoritmo de busca linear e procurando por qualquer chave específica diversas vezes. Podemos usar o “Algoritmo de pesquisa binária” se a matriz for uma matriz classificada.
Suponha que a matriz consista em 10 mil números e o elemento de destino seja encontrado no 5000º índice. Portanto, o algoritmo tentará comparar 5000 elementos. Agora, as comparações são tarefas que exigem muita CPU. Para otimizar o algoritmo de busca linear, temos duas opções.
- Transposição
- Mover para Frente
Transposição:
Neste método, trocaremos o elemento de pesquisa pelo seu elemento anterior no array. Por exemplo, digamos que você tenha um array como o seguinte:
Dados[] = {1,5,9,8,7,3,4,11}
Agora queremos pesquisar 4. Etapas de Transposição:
Passo 1) “4” é encontrado no índice 6. Foram necessárias seis comparações.
Passo 2) Troque dados[6] e dados[5]. Então a matriz de dados ficará assim:
Dados[] = {1,5,9,8,7,4,3,11}
Passo 3) Pesquise 4 novamente. Encontrado no índice 5. Desta vez foram necessárias cinco comparações.
Passo 4) Troque dados [5] e dados [4]. Então a matriz de dados ficará assim:
Dados [] = {1,5,9,8,4,7,3,11}
Agora, se você notar, quanto mais frequente uma chave é pesquisada, mais diminui o índice. Assim, diminuindo o número de comparações.
Vá para a frente:
Neste método, trocamos o elemento de pesquisa no 0º índice. Porque se for pesquisado novamente, podemos encontrá-lo no tempo O(1).
Aplicação do Algoritmo de Pesquisa Linear
Aqui estão alguns aplicativos de pesquisa linear que podemos usar.
- Para arrays pequenos ou apenas alguns elementos na lista, é mais fácil usar a pesquisa linear.
- O método de pesquisa linear pode ser usado de forma simples ou arrays multidimensionais ou outras estruturas de dados.
- Geralmente, a busca linear é simples e eficiente para realizar uma busca nos dados “não ordenados”. Podemos buscar facilmente um único dado de uma lista não ordenada fornecida.
