Page 353 - Informatica dalla A a Z

M=(inizio + fine) / 2;

if a[m]==k)
trovato = true;
else
if (k>a[m])
inizio=m+1;
else
if (k<[m])
fine=m-1;
} while ((!trovato)&&(inizio <= fine));
return trovato;
}
La procedura potrebbe anche essere scritta così:

int ricercaBinaria(int vet[1, int N, int K)
{

int inizio, fine, centro;
inizio = 0;
fine = N—l;
while (inizio <= fine)
{
centro = (inizio + fine )/2; // elemento centrale
if (vet[centro] == K)
return.centro; //valore-K trovato in posizione centro
if (vet[centro] < K)
inizio = centro + 1;
else
fine = centro — 1;
}
// se l’esecuzione arriva a guesto punto significa che il va-
lore k NON è presente nel vettore:
return -l;
}

Come si può notare, a causa dell’avanzamento del processo di ricerca, gli indici, Inizio e

Fine, subiscono uno spostamento, rispettivamente, in avanti ed indietro, tendendo a con-
vergere.
Se a causa della convergenza di cui sopra, il primo indice dovesse superare il secondo, que-
sto indicherà che la chiave da cercare non è presente.
Vediamo un altro modo:
int ricerca_binaria (int V[ ], int K, int inizio, int fine)

{
int centro;

349