Ricerca sequenziale con sentinella

di

Si tratta di una versione leggermente migliorata dell’algoritmo di ricerca sequenziale.

Il confronto (i <= n) ripetuto a ogni passo può essere eliminato se si introduce la sentinella, la chiave della ricerca, alla prima posizione libera nell’array.

Il ciclo si chiude comunque nel caso in cui la chiave non esista.

Function Sentinella(V: Vettore; N: Integer; K: Real): Integer;
Var
    i: Integer;
Begin
    i:=1;
    V[N+1]:=K;
    While(V[i] <> K) Do
        i:=i+1;
    If(i > N) Then
        Sentinella:=0
    Else
        Sentinella:=i;
End;

Se l’array è ordinato si può introdurre un ulteriore miglioramento…

Function Sentinella(V: Vettore; N: Integer; K: Real): Integer;
Var
    i: Integer;
Begin
    i:=1;
    V[N+1]:=K;
    While(V[i] < K) do
        i:=i+1;
    If(i > N) Or (V[i] > K) Then
        Sentinella:=0
    Else
        Sentinella:=i;
End;