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;

}