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;
}
