Pesquisa Linear

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

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.

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.