Ricerca sequenziale con sentinella

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;