Scrivere un programma in linguaggio C che implementi la seguente funzione:
- int ricercaBinaria(int valore, int vettore[], int primo, int ultimo); che preso in input un intero da cercare ed un vettore di interi ordinato, ricorsivamente applichi l'algoritmo della ricerca binaria e restituisca il valore qualora presente oppure "-1" qualora assente.
main.c
#include "dichiarazioni.h"
int main()
{
int *v, dimensione, i, scelta, ricercato, primo, ultimo, risultato;
printf("RICERCA BINARIA - ALGORITMO RICORSIVO \n\n");
printf("Dimensione array: ");
scanf("%d", &dimensione);
//Allocazione dinamica della memoria
v = (int *) malloc (dimensione * sizeof(int));
for(i = 0; i < dimensione; i++)
{
printf("v[%d] = ", i);
scanf("%d", &v[i]);
}
printf("Array caricamento di dimensione: %d\n", dimensione);
for(i = 0; i < dimensione; i++)
{
if(i == 0)
primo = v[i];
if(i == dimensione - 1)
ultimo = v[i];
printf("v[%d] = %d\n", i, v[i]);
}
printf("%d e' il primo elemento dell'array.\n", primo);
printf("%d e' l'ultimo elemento dell'array.\n", ultimo);
printf("Inserisci l'elemento (intero) da ricercare: ");
scanf("%d", &ricercato);
//Invocazione della funzione
risultato = ricercaBinaria(ricercato, v, primo, ultimo);
if(risultato < 0)
printf("Il numero %d non e' presente all'interno del vettore.", ricercato);
else
printf("Il numero %d e' presente all'interno del vettore.", ricercato);
return 0;
}
funzioni.c
#include "dichiarazioni.h"
int ricercaBinaria(int valore, int vettore[], int primo, int ultimo)
{
int i = 0;
if(valore == vettore[i])
return valore;
if((valore != vettore[i])&&(vettore[i] == ultimo))
return -1;
i++;
//Chiamata della funzione ricorsiva
ricercaBinaria(valore, vettore, primo, ultimo);
}
Il programma viene compilato senza alcun errore, però in compilazione mi dice
Errore di segmentazione (core dump creato).
Questo perché ogni volta che la funzione richiama se stessa tutte le variabili vengono inizializzate nuovamente e quindi l'indice i starebbe sempre fisso a zero. Corretto?
Vi posto qui la soluzione del prof:
#include "es7-ex5.h"
int ricercaBinaria(int valore,int vettore[],int primo,int ultimo)
{
int mid,c=0;
if(primo<=ultimo)
{
mid=(primo+ultimo)/2;
if(valore==vettore[mid])
{
c=1;
}
else
{
if(valore<vettore[mid])
{
return ricercaBinaria(valore,vettore,primo,mid-1);
}
else
return ricercaBinaria(valore,vettore,mid+1,ultimo);
}
}
return c;
}
Io, però, vorrei correggere la mia! Dunque, come faccio ad effettuare la ricorsione senza che ogni volta le variabili perdano il loro precedente contenuto?
Grazie