Lezione dell'8 Gennaio 2002

Gli array - ricerca binaria

COSA E' STATO FATTO A LEZIONE

Questo documento contiene un RIASSUNTO degli argomenti presentati a lezione. Per eventuali chiarimenti rivolgersi al docente.

Ricerca binaria

Supponiamo di essere in un contesto di programma in cui sono disponibili le seguenti dichiarazioni. 

const

   vettLenght = 1000; {Capacita' del tipo-array vett}


type

   vett = array [0..vettLenght-1] of integer;


var

   v1 : vett;
   v1Size : integer; {Numero di elementi utilizzati nell'array v1}

Prima versione (PASCAL STANDARD)

{
  AI: 0 <= vSize <= vettLength-1 AND
      v[0..vSize-1] e' ordinato in ordine non decrescente
  AF: restituisce un i tale che v[i]=x, -1 se un tale i non esiste
}
function ricercaBinaria (x:integer;
                          var v:vett; 
                          vSize:integer)

var
   i:integer;
   lo,hi:integer;
   trovato:boolean;

begin
   lo:=0;
   hi:=vSize-1;
   trovato:=false;

   { 
     IC: se esiste un j tale che v[j]=x allora lo <= j <= hi
         AND
         trovato = (x=v[i])
   }
   while (lo <= hi) AND (not trovato) do
      begin
         i:=(hi+lo) div 2;
         if x=v[i] then trovato:=true
         else if v[i] < x then lo:=i+1
         else hi:=i-1;
      end;
  
  if trovato then ricercaBinaria:=i
             else ricercaBinaria:=-1;
end;

Seconda versione (TURBO PASCAL)

{
  AI: 0 <= vSize <= vettLength-1 AND
      v[0..vSize-1] e' ordinato in ordine non decrescente
  AF: restituisce un i tale che v[i]=x, -1 se un tale i non esiste
}
function ricercaBinaria (x:integer;
                          var v:vett; 
                          vSize:integer)

var
   i:integer;
   lo,hi:integer;

begin
   lo:=0;
   hi:=vSize-1;
   i:=vSize;

   { 
     IC: se esiste un j tale che v[j]=x allora lo <= j <= hi
   }
   while lo <= hi do
      begin
         i:=(hi+lo) div 2;
         if x=v[i] then begin ricercaBinaria:=i; exit; end
         else if v[i] < x then lo:=i+1
         else hi:=i-1;
      end;
  
   ricercaBinaria:=-1;
end;

Complessita` computazionale concreta in tempo e in spazio della function "ricercaBinaria"

Complessita' in spazio: entambe le versioni della function ricercaBinaria
NOTA: il vettore v e' passato per referenza (var) .

Complessita' in tempo: entambe le versioni della function ricercaBinaria hanno complessita' in tempo che e':

ESERCIZI DA SVOLGERE

Per eventuali chiarimenti rivolgersi ai docenti.
  1. Scrivere, compilare, ed eseguire un programma Pascal che legge un array V di N interi (N stabilito dall'utente), un intero X, e stampa il risultato della chiamata: "ricercaBinaria(X,V,N)".
    ATTENZIONE: PROVARE ENTRAMBE LE VERSIONI DELLA function.