Pesquisa Linear

Harshit Jindal 12 outubro 2023
  1. Algoritmo de pesquisa linear
  2. Exemplo de pesquisa linear
  3. Implementação do algoritmo de pesquisa linear
  4. Complexidade do algoritmo de pesquisa linear
Pesquisa Linear

A pesquisa linear é o algoritmo de pesquisa mais simples. Também é chamada de busca sequencial porque, neste algoritmo, procuramos um elemento percorrendo todo o array e comparando cada elemento com o item desejado para encontrar uma correspondência. Se o elemento desejado for encontrado, o índice ou esse elemento é retornado; caso contrário, continuamos a pesquisar até esgotar o array. Também podemos procurar várias ocorrências de um item dentro de um array. É usado principalmente para pesquisar itens dentro de uma matriz não classificada. Não é usado de forma prática porque é muito mais lento do que a pesquisa binária.

Algoritmo de pesquisa linear

Vamos supor que temos um array não classificado A[] contendo n elementos, e queremos encontrar um elemento - X.

  • Percorra todos os elementos dentro da matriz, começando do elemento mais à esquerda usando um loop for e faça o seguinte:
    • Se o valor de A[i] corresponder a X, retorne o índice i. (Se houver vários elementos correspondendo a X, em vez de retornar o índice i, imprima todos indexe ou armazene todos os índices em uma matriz e retorne essa matriz.)
    • Caso contrário, vá para o próximo elemento.
    • Se estiver no último elemento da matriz, saia do loop for.
  • Se nenhum dos elementos corresponder, então retorna -1.

Exemplo de pesquisa linear

Suponha que temos o array: (5, 3, 4, 2, 1, 6).

  • Caso 1: Queremos procurar X = 5.

O primeiro elemento em si é uma correspondência e retornamos o índice 0. (Melhor caso)

  • Caso 2: Queremos procurar X = 1.

Percorremos a matriz e alcançamos o índice 4 para encontrar uma correspondência e retornar esse índice. (Caso Médio)

  • Caso 3: queremos procurar X = 9

Percorremos a matriz, mas não encontramos uma correspondência quando alcançamos o último elemento da matriz. Retornamos -1. (Pior caso)

Implementação do algoritmo de pesquisa linear

Algoritmo de pesquisa linear para correspondência única

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) return i;
  }
  return -1;
}

int main() {
  int n = 5;
  int arr[] = {2, 4, 0, 1, 9};
  int x = 1;
  int result = search(arr, n, x);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index: " << result;
}

Algoritmo de pesquisa linear para múltiplas correspondências

#include <bits/stdc++.h>
using namespace std;

vector<int> search(int arr[], int n, int x) {
  vector<int> ans;
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      ans.push_back(i);
    }
  }
  return ans;
}

int main() {
  int n = 9;
  int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
  int x = 1;
  vector<int> res = search(arr, n, x);
  if (res.empty()) {
    cout << "Element not found!!";
  } else {
    cout << "Element found at ";
    for (int i = 0; i < res.size(); i++) {
      cout << res[i] << " ";
    }
  }
}

Complexidade do algoritmo de pesquisa linear

Complexidade de tempo

  • Caso Médio

A complexidade de tempo do algoritmo de pesquisa linear é O(n).

  • Melhor caso

O melhor caso de complexidade de tempo é O(1). Ocorre quando o elemento a ser pesquisado é o primeiro elemento presente dentro do array.

  • Pior caso

O pior caso ocorre quando o elemento que procuramos não está presente no array ou está no último índice do array. O pior caso de complexidade de tempo é O(n).

Complexidade do Espaço

A complexidade espacial desse algoritmo depende do número de correspondências e da implementação usada. Em geral, a complexidade do espaço é declarada como O(1), mas pode ser maior se vários índices correspondentes forem armazenados dentro de uma matriz.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn