Pesquisa Linear: Python, C++ Exemplo

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.