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, buscar a altura mínima em uma lista de alturas ou a maior marca em uma lista ou matriz de números. Alguns algoritmos de busca populares incluem "Busca Linear", "Busca Binária", "Busca por Salto", "Busca de Fibonacci", etc.

O que é pesquisa linear?

Pesquisa Linear é um dos algoritmos de busca mais simples. A partir de uma lista ou array, ele busca o elemento desejado um por um. A busca linear itera sobre toda a lista e verifica se algum elemento específico é igual ao elemento procurado. Também é chamada de busca 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 em questão 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?

Vamos supor que temos um array contendo números inteiros. A tarefa é encontrar um número específico nesse array.

• 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 com 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 nº 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.

Apelido Code para o algoritmo de busca sequencial

O pseudocódigo a seguir descreve a lógica da busca linear descrita acima. Ele percorre o array a partir do primeiro índice e retorna a posição em que houver uma correspondência; caso contrário, retorna -1.

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 a negative index is not valid
    return -1

C++ Code Exemplo de pesquisa linear

Aqui está um completo C++ Programa que implementa a busca sequencial e imprime o índice do valor pesquisado.

#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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Exemplo de pesquisa linear

A mesma lógica em Python Utiliza um único loop sobre os índices da lista e retorna a posição do elemento correspondente.

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

De forma geral, a complexidade de tempo significa a quantidade de tempo de CPU necessária para executar uma determinada tarefa. No algoritmo de busca linear, a tarefa consiste em encontrar a chave de busca entre os elementos do vetor.

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:

Suponhamos que precisamos realizar uma busca linear em um array de tamanho "n". Podemos encontrar o item de busca entre os índices 0 e n-1. No pior cenário, o algoritmo tentará encontrar correspondências entre todos os elementos do array e o elemento de busca.

Nesse caso, a complexidade no pior caso será O(n). Aqui, “O” — notação O grande — significa a função de complexidade.

Complexidade temporal da pesquisa linear no cenário Melhor-Case:

Vamos supor que estamos procurando um elemento que reside na primeira posição do array. Nesse cenário, o algoritmo de busca linear não buscará por todos os n elementos do array. 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 de 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 busca pode ser realizada várias vezes ao longo do ciclo de vida do programa. Também é possível que estejamos executando o algoritmo de busca linear e procurando por uma 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 busca com o elemento anterior na matriz. Por exemplo, digamos que você tenha uma matriz como a 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 data[5] e data[4]. Então o array de dados ficará assim:

Dados[] = {1,5,9,8,4,7,3,11}

Agora, observe que quanto mais frequentemente uma chave é pesquisada, mais o índice diminui. Consequentemente, o número de comparações também diminui.

Vá para a frente:

Neste método, trocamos o elemento de busca para o índice 0. Porque se for pesquisado novamente, podemos encontrá-lo em tempo O(1).

Aplicação do Algoritmo de Pesquisa Linear

Aqui estão alguns aplicativos de pesquisa linear que podemos usar.

• Para arrays de tamanho reduzido ou com poucos elementos na lista, é mais fácil usar a busca 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.

Perguntas Frequentes