Ricerca sequenziale con sentinella

Da Wikipedia, l'enciclopedia libera.

Questo algoritmo è una variazione della ricerca sequenziale.

Consiste nell'inserire, come ultimo elemento dell'array, l'elemento cercato. In questo modo potremo fermare la ricerca quando l'elemento verrà trovato, evitando il controllo relativo al numero di elementi contenuti nell'array.

Eccone un'implementazione in linguaggio C:

int ricercaSequenzialeConSentinella(int lista[], int x, int n) {

    int i;
 
    lista[n]=x;
    for (i=0; lista[i]!=x; i++) ;
 
    if (i<n)
       return i;
    else
       return -1;

}