Ricerca sequenziale

di

Individuare la posizione di un certo elemento all’interno di una sequenza data.

Posizione di un valore k all’interno di un array v

Function Posizione(V: Vettore; N: Integer; K: Real): Integer;
Var
   i, Risp: Integer;
Begin
   Risp:=0;
   For i:=1 to N do
      If(V[i] = K) Then
         Risp:=i;
   Posizione:=Risp;
End;

Purtroppo restituisce la posizione dell’ultimo valore presente.

Posizione di un elemento (la prima…)

Function Posizione(V: Vettore; N: Integer; K: Real): Integer;
Var
   i, Risp: Integer;
Begin
   i:=1;
   Risp:=0;
   While(i <= N) And (Risp = 0) Do
      Begin
         If(V[i] = K) Then
            Risp:=i;
         i:=i+1;
      End;
   Posizione:=Risp;
End;

Semplifico il ciclo

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

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 cercato

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

Ricerca sequenziale con sentinella

Si tratta di una versione leggermente migliorata dell'algoritmo.

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;

Array ordinato

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;

Analisi della complessità, in tempo e asintotica, dell'algoritmo di ricerca sequenziale.

Il codice analizzato è il seguente

Function ricercaSequenziale(V: Vettore; N: Integer; K: Real): Integer;
Var
   i: Integer;
Begin
   i:=1;                              (* 1 *)
   While(i <= N) And (V[i] <> K) Do   (* 2, 3, 4 *)
      i:=i+1;                         (* 5, 6 *)
   If(i > N) Then                     (* 7 *)
      ricercaSequenziale:=0           (* 8 *)
   Else
      ricercaSequenziale:=i;          (* 9 *)
End;

presenta operazioni di

  • assegnamento: 1, 5, 8, 9
  • confronto: 2, 4, 7
  • aritmetico-logiche: 3, 6

Il tempo totale richiesto da questo sottoprogramma alla CPU è

T = T1+(T2+T3+T4+T5+T6)*x+(T2+T3+T4)+T7+T8|9

con

  • (T2+T3+T4+T5+T6), le operazioni svolte ad ogni passo del While
  • x, il numero di volte che viene eseguito il While (da 0 a n)
  • (T2+T3+T4), quando K viene individuato alla posizione i-esima oppure il vettore finisce
  • T8|9, una delle due istruzioni finali

Per semplificare i calcoli si decide di trascurare le differenze esistenti tra i tempi di esecuzione delle diverse operazioni e di stabilire un tempo costante per tutte, allora

T = 6+5x

I valori effettivi di T sono

  • vettore vuoto: T1+(T2+T3+T4)+T7+T8 = 6
  • elemento in 1° posizione: T1+(T2+T3+T4)+T7+T9 = 6
  • elemento in 2° posizione: T1+[T2+T3+T4+T5+T6]+(T2+T3+T4)+T7+T9 = 6+5*1 = 11
  • elemento in 3° posizione: T1+[T2+T3+T4+T5+T6]*2+ ... = 6+5*2 = 16
  • ...
  • elemento in ultima posizione: 6+5*(n-1)
  • elemento non presente: 6+5n

Analizziamo i casi più interessanti

  • Caso ottimo, quando il vettore è vuoto oppure l'elemento K compare in 1° posizione: T=6
  • Caso pessimo, se l'elemento K non è presente: T=6+5n
  • Caso medio, supponiamo di effettuare n ricerche con l'elemento presente alle diverse posizioni: T=3.5+2.5n

Conclusioni

Il tempo richiesto è, tranne che nei casi banali, una funzione lineare di n, il numero di elementi presenti nel vettore

T(n)=c1+c2n

I valori delle due costanti c1 e c2 sono modesti e comunque poco significativi.

I calcoli per il caso medio

T=[(6+5*0)+(6+5*1)+(6+5*2)+...+(6+5(n-1))]/n
=[6n+5(1+2+...+n-1)]/n
=[6n+5(n-1)*n/2]/n
=6+5(n-1)/2
=6+5/2*n-5/2
=7/2+5/2*n
=3.5+2.5*n

Osserva che
1+2+...n=n(n+1)/2