2001 – 8 bis

Il seguente frammento di programma è stato scritto per effettuare la ricerca di un elemento identificato dalla variabile chiave in un array ordinato (in ordine crescente) vett con n componenti intere.
Se l’elemento chiave è presente nell’array allora il programma deve fornire in uscita il valore di un indice dell’array il cui valore è pari al valore di chiave; se l’elemento chiave non è presente allora il programma deve ritornare il valore –1.

Il frammento di programma seguente non è sempre corretto; tuttavia è possibile ottenere un programma che risponde alle specifiche modificando una sola istruzione.
Indicate il numero di istruzione e come deve essere scritta. (Potete, per semplicità, supporre che n sia pari a 4).

int ricerca(int vett[], int n, int chiave)
{
    int inf=0, sup=n-1, x;
    while(inf <= sup)
    {
        x=(inf+sup)/2;
        if(chiave < vett[x])
            sup=x–1;
        else if(chiave > vett[x])
            inf=x;
        else
            return x;
   }
   return -1;
}

Soluzione: inf=x; diventa inf=x+1;


Si tratta dell’algoritmo di ricerca binaria…