Algoritmo per la ricerca binaria ricorsiva.

Loading

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]

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