Ciao a tutti!
Scusate il disturbo ma sono alle brighe con questo esercizio in linguaggio C:
Ecco il testo:
Nel file ricerca.c implementare la definizione della funzione :
extern int ricerca_binaria (const int *v, size_t n, int x);
La funzione accetta un puntatore ad un vettore v di interi, contenente n elementi e deve ricercare il valore x nel vettore. Il vettore è ordinato dal calore più piccolo al valore più grande. Se l'elemento è presente nel vettore, la funzione ritorna l'indice dell'elemento nel vettore, altrimenti ritorna -1. Se l'elemento è presente più volte, l'indice sarà quello di uno qualsiasi degli elementi con il valore x.
La particolarità di questa funzione è che la ricerca avviene in modo dicotomico. Questo vuol dire che si definisce un intervallo di ricerca [primo,ultimo] (dove all'inizio primo sarà 0 e ultimo sarà n-1). Da questo si calcola il punto medio m (arrotondando all'intero inferiore). Se la posizione m contiene il valore cercato, la funzione termina (abbiamo trovato infatti il valore x in posizione m). Altrimenti si verifica se x può essere a sinistra (valori minori) o a destra (valori maggiori) di m. Nel primo caso l'intervallo diventa [primo,m-1], nel secondo caso diventa [m+1,ultimo]. Quindi la ricerca continua in modo analogo sul nuovo intervallo. Se durante la ricerca primo diventa maggiore di ultimo, x non è presente nel vettore.
Allora io ho scritto il seguente codice C:
#include <stdio.h>
int ricerca_binaria (const int *v, size_t n, int x)
{
size_t i = 0;
int media = 0;
int primo = 0;
int ultimo = n-1;
for( i=0; i != (n-1); i++)
{
media = (primo + ultimo) / 2;
if ( v[media] == x)
return i = media;
if ( v[media] > x)
{
primo = 0;
ultimo = media - 1;
}
else
{
primo = media + 1;
ultimo = n-1;
}
if ( primo > ultimo)
return -1;
}
return i;
}
Allora sembra che funzioni.. Solo che se per esempio cerco un valore x che non c'è all'interno del vettore, invece di ritornare -1, mi ritorna un valore a caso..
Come posso correggerlo?