Fare internet

E' come il lego, più pezzi ho più sono allegro
Seguci su Facebook Seguici su Twitter Iscrivita ai nostri Feed      Mandaci una mail

Algoritmo per la ricerca binaria ricorsiva.

Scritto da Fare-internet il 5 maggio 2011 condividi condividi

Di seguito riportiamo l’agoritmo che esegue la ricerca binaria ricorsiva.

La ricerca binaria consiste nell’individuare un numero all’interno di un vettore di numeri ordinato in maniera crescente, dimezzando lo spazio di ricerca di volta in volta, per il corretto funzionamento dell’algoritmo sottolineamo che il vettore deve essere ordinato, altrimenti non otterremo risultati corretti.

Per la descrizione di tale algoritmo non utilizzeremo un linguaggio preciso, ma il così detto pseudocodice, cioè un linguaggio che utilizza le strutture dei linguaggi di programmazione senza utilizzarne la sintassi precisa.

Una fuzione ricorsiva è una funzione che al suo interno richiama se stessa, possiamo ora passare allo pseudocodice:

function ricercaRic(sx,dx,arr[],trova){

//sx e dx sono i 2 indici tra cui cercare
//arr è l’array ordinato in cui cercare
//trova è il numero da trovare

    if (sx>dx){
        trovato=false;
    } else {
        m = (dx+sx) / 2;// in caso di numero non intero riportiamo
                                   // la parte inferiore
                                   // (es. per 3+4 = 7, 7/2 = 3,5 =>3)
        if (arr[m]==trova)
            trovato=true;
        else if(arr[m]<trova)
            ricercaRic(m+1,dx,arr[],trova);
        else    
            ricercaRic(sx,m-1,arr[],trova);
    }
    return trovato;
}
 

Per povarlo potete cercare il valore 19 nel seguente array e vedere cosa succede:

arr[]=(1,2,3,11,18,19,20);

la chiamata iniziale sarà:
ricercaRic(0,7,arr[],19)

quelle ricorsive saranno successivamente:
ricercaRic(4,7,arr[],19);
ricercaRic(6,7,arr[],19); -> trovato

Twitter