Ricerca sequenziale
Posizione di un valore k all'interno di un array v
FUNZIONE posizione(IN REALE v[], IN REALE k): INTERO
INIZIO
INTERO risp=-1,
i,
n=v.QUANTI
PER(i DA 0 A n-1 PASSO +1)
SE(v[i] == k) ALLORA
risp=i
posizione=risp;
FINE
INIZIO
INTERO risp=-1,
i,
n=v.QUANTI
PER(i DA 0 A n-1 PASSO +1)
SE(v[i] == k) ALLORA
risp=i
posizione=risp;
FINE
Purtroppo restituisce la posizione dell'ultimo valore presente.
Posizione di un elemento (la prima...)
FUNZIONE posizione(IN Reale v[], IN Reale k): INTERO
INIZIO
INTERO risp=-1,
i=0,
n=v.QUANTI
MENTRE(i < n AND risp == -1)
INIZIO
SE(v[i] == k) ALLORA
risp=i
i=i+1
FINE
posizione=risp
FINE
INIZIO
INTERO risp=-1,
i=0,
n=v.QUANTI
MENTRE(i < n AND risp == -1)
INIZIO
SE(v[i] == k) ALLORA
risp=i
i=i+1
FINE
posizione=risp
FINE
Semplifo il ciclo
FUNZIONE posizione(IN REALE v[], IN REALE k): INTERO
INIZIO
INTERO i=0,
n=.v.QUANTI
MENTRE(i < n AND v[i] != k)
i=i+1
SE(i == n) ALLORA
posizione=-1
ALTRIMENTI
posizione=i
FINE
INIZIO
INTERO i=0,
n=.v.QUANTI
MENTRE(i < n AND v[i] != k)
i=i+1
SE(i == n) ALLORA
posizione=-1
ALTRIMENTI
posizione=i
FINE
La ricerca sequenziale effettua una scansione dell'array finché non trova il valore richiesto, se presente, o l'array finisce.
Array ordinato
Se l'array è ordinato e l'elemento non compare la ricerca sequenziale può essere interrotta se l'elemento esaminato è maggiore di quello cercatoFUNZIONE posizione(IN REALE v[], IN REALE k): INTERO
INIZIO
INTERO i=0,
n=v.QUANTI
MENTRE(i < n AND v[i] < k)
i=i+1
SE(i == n OR v[i] > k) ALLORA
posizione=-1
ALTRIMENTI
posizione=i
FINE
INIZIO
INTERO i=0,
n=v.QUANTI
MENTRE(i < n AND v[i] < k)
i=i+1
SE(i == n OR v[i] > k) ALLORA
posizione=-1
ALTRIMENTI
posizione=i
FINE
Con sentinella
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 (la n-esima, senza modificare n...); in questo modo il ciclo si chiude comunque nel caso in cui la chiave non esista.FUNZIONE sentinella(IN REALE v[], IN REALE k): INTERO;
INIZIO
INTERO i=0,
n=v.QUANTI
V[n] = K
MENTRE(V[i] <> K)
i = i+1
SE(i == N) ALLORA
Sentinella = -1
ALTRIMENTI
Sentinella = i
FINE
INIZIO
INTERO i=0,
n=v.QUANTI
V[n] = K
MENTRE(V[i] <> K)
i = i+1
SE(i == N) ALLORA
Sentinella = -1
ALTRIMENTI
Sentinella = i
FINE
Array ordinato
FUNZIONE sentinella(IN REALE v[], IN REALE k): INTERO;
INIZIO
INTERO i=0,
n=v.QUANTI
V[n] = K
MENTRE(V[i] < K)
i = i+1
SE(i == N OR V[i] > K) ALLORA
Sentinella = -1
ALTRIMENTI
Sentinella = i
FINE
INIZIO
INTERO i=0,
n=v.QUANTI
V[n] = K
MENTRE(V[i] < K)
i = i+1
SE(i == N OR V[i] > K) ALLORA
Sentinella = -1
ALTRIMENTI
Sentinella = i
FINE
