Ricerca sequenziale

Da Wikipedia, l'enciclopedia libera.

In informatica la ricerca sequenziale è un algoritmo utilizzabile per trovare un elemento in un insieme non ordinato (esiste però una variante: la Ricerca sequenziale con sentinella).

Quando bisogna effettuare una ricerca in una struttura dati del genere si effettua la scansione dell'array sequenzialmente. Il problema grosso di una struttura dati del genere e che per capire se l'elemento non c'è bisogna effettuare una scansione totale dell'array (questo da un costo lineare all'algoritmo dato che nel caso peggiore dobbiamo leggere tutti i dati).

Ecco un'implementazione in C di detto algoritmo. Il parametro insieme è un array in cui cercare, x è l'elemento da cercare e infine n è il numero di elementi contenuti nell'array.

int ricercaSequenziale(int insieme[], int x, int n) {
 
     int i;
 
     i = 0;
     while (i<n && x!=insieme[i]) i++;
 
     if (i==n) return -1;
 
     return i;
 
 }

È anche possibile iniziare la ricerca dall'ultimo elemento, in direzione inversa. Ciò è utile se è più probabile che l'elemento si trovi verso la fine dell'array:

int ricercaSequenzialeInversa(int insieme[], int x, int n) {
 
     int i;
 
     i = n-1;
     while (i>=0 && x!=insieme[i]) i--;
 
     if (i<0) return -1;
 
     return i;
 
 }