Ricerca lineare

1. Algoritmo di ricerca lineare
2. Esempio di ricerca lineare
3. Implementazione dell’algoritmo di ricerca lineare
4. Complessità algoritmo di ricerca lineare

La ricerca lineare è l’algoritmo di ricerca più semplice. Viene anche chiamata ricerca sequenziale perché, in questo algoritmo, cerchiamo un elemento attraversando l’intero array e confrontando ogni elemento con l’elemento desiderato per trovare una corrispondenza. Se viene trovato l’elemento desiderato, viene restituito l’indice o quell’elemento; in caso contrario, continuiamo a cercare finché non esauriamo l’array. Possiamo anche cercare più occorrenze di un elemento all’interno di un array. Viene utilizzato principalmente per cercare elementi all’interno di un array non ordinato. Non viene utilizzato praticamente perché è molto più lento della ricerca binaria.

Algoritmo di ricerca lineare

Supponiamo di avere un array non ordinato A[] contenente n elementi e di voler trovare un elemento - X.

Esempio di ricerca lineare

Supponiamo di avere l’array: (5, 3, 4, 2, 1, 6).

• Caso 1: vogliamo cercare X = 5.

Il primo elemento stesso è una corrispondenza e restituiamo l’indice 0. (Caso migliore)

• Caso 2: vogliamo cercare X = 1.

Attraversiamo l’array e raggiungiamo l’indice 4 per trovare una corrispondenza e restituire quell’indice. (Caso medio)

• Caso 3: vogliamo cercare X = 9

Attraversiamo l’array ma non troviamo una corrispondenza quando raggiungiamo l’ultimo elemento dell’array. Torniamo -1. (Caso peggiore)

Implementazione dell’algoritmo di ricerca lineare

Algoritmo di ricerca lineare per corrispondenza singola

#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 di ricerca lineare per più corrispondenze

#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] << " ";
    }
  }
}

Complessità algoritmo di ricerca lineare

Complessità temporale

• Case nella media

La complessità temporale dell’algoritmo di ricerca lineare è O(n).

• Caso migliore

La complessità temporale nel migliore dei casi è O(1). Si verifica quando l’elemento da ricercare è il primo elemento presente all’interno dell’array.

• Nel peggiore dei casi

Il caso peggiore si verifica quando l’elemento che stiamo cercando non è presente all’interno dell’array o si trova all’ultimo indice dell’array. La complessità temporale nel caso peggiore è O(n).

Complessità spaziale

La complessità dello spazio di questo algoritmo dipende dal numero di corrispondenze e dall’implementazione utilizzata. In generale, la complessità dello spazio è indicata come O(1) ma può essere maggiore se più indici corrispondenti sono memorizzati all’interno di un array.