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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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; |