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…