[C] aiuto con ricerca binaria ricorsiva...help me :-(

[D4rkAng3l]

Ciao,
sono disperato, devo fare un esercizio che esegua la ricerca binaria di un valore in un array mediante una funzione ricorsiva...il mio programma si compila ma mi dà strani valori....cos'è che non và? La logica è giusta?

Io l'ho pensato così:

1) ho un array ordinato di n element

2)chiamo la mia funzione passandogli il puntatore al vettore, la chiave da ricercare, l'elemento più basso da cui aprtire e quello più alto dove arrivare)

3)La funzione essendo ricorsiva ha dei casi base che nel mio caso sono:
l'elemento è stato trovato e restituisce la posizione nel vettore al chiamante
l'elemento non è stato trovato e restituisce -1 al chiamante

4)Se la chiave è maggiore dell'elemento di mezzo invoca nuovamente la funzione passandogli come elemento più basso il vecchio elemento di mezzo + 1 e come elemento più alto il vecchio elemento più alto

Se la chiave è minore dell'elemento di mezzo invoca nuovamente la funzione passandogli come elemento più basso il vecchio elemento più basso e come elemento di mezzo il vecchi elemento di emzzo-1

cmq il codice è questo, forse s capisce meglio anche il concetto:

/* Ricerca binaria in un arrya mediante l'uso di una funzione ricorsiva */

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

/* La funzione riceve l'indirizzo al primo elemento del vettore, la chiave,
   l'elemento da cui partire, e l'elemento a cui arrivare */
int binric(int *, int, int, int);

int main(){
    int a[SIZE] = {1,2,3,4,5,6,7,8,9,10};
    int key, risultato;
    
    printf("Inserire un valore da ricercare nell'array: ");
    scanf("d", &key);
    
    risultato = binric(a, key, 0, SIZE-1);
    
    if(risultato == -1)
        printf("L'elemento inserito non è presente nel vettore\n");
    else
        printf("L'elemento inserito si trova nella %d locazione\n", risultato);
    
    system("PAUSE");
    return 0;
}

int binric(int b[], int chiave, int low, int hight){
    
    int midle;  // Valore di mezzo
    midle = (low+hight)/2;
    
    /* Casi base: se ha trovato la chiave o se non ha trovato la chiav nel
        vettore */
    if(chiave == b[midle])    // elemento trovato
        return midle;
    else if(hight <= low)    // elemento non trovato
        return -1;
    
    /* Se deve continuare la ricerca rinvoca la funzione binric ricorsivamente
       fino al ragiungimento di uno dei due casi base */
       
    else if(chiave >= b[midle])
        binric(b, chiave, midle+1, hight);
    else
        binric(b, chiave, low, midle-1);
}

Grazie
Andrea

[Brazorv]

prova cambiare le ultime righe della binric così

    else if(chiave >= b[midle])
        return binric(b, chiave, midle+1, hight);
    else
        return binric(b, chiave, low, midle-1);

[D4rkAng3l]

mmmm così mi dic sempre che l'elemento non è presente nel vettore

come mai?
cmq la logica della ricorsione è corretta?

[kk3z]

No, non è corretto, nel tuo codice il primo "middle" è 4, se il numero nell'array è in una posizione > 4, low diventa 5 e height 9. Il middle quindi è 7, ma così hai saltato 2 elementi dell'array (5 e 6) senza controllarli

PS: consigliare di cliccare sui banner di google è un bel modo per farsi bannare da adsense