Probabilmente tutti quelli che hanno studiato programmazione a scuola si sono trovati, chi prima chi poi (se non addirittura fin dalla prima lezione) a dover affrontare il problema della ricerca binaria. La sua formulazione è semplicissima e la soluzione è apprezzabile da tutti, anche se non si ha alcun background tecnico. Ma partiamo dall’inizio e scopriamo di cosa si tratta.

La definizione del problema

La definizione può essere data anche senza dover usare termini informatici, infatti, il problema della ricerca binaria (o dicotomica) è quello di trovare un elemento all’interno di una collezione ordinata di elementi omogenei.

Supponiamo di avere uno scaffale pieno di libri ordinati rigorosamente in ordine alfabetico, e di doverne ricercare uno in particolare: qual è secondo voi l’approccio migliore?

Chi di voi sente che la domanda è incompleta alzi la mano! Ed infatti lo è: non possiamo stabilire l’approccio migliore in termini assoluti, ma dobbiamo capire “migliore” rispetto a che cosa!
Per esempio visto che io adoro le biblioteche per me il modo migliore di cercare un libro è quello che ci mette più tempo! Per qualcun’altro l’approccio migliore è quello invece di trovarlo in meno tempo possibile, oppure minimizzando il tragitto percorso durante la ricerca.

Tutto questo vale alla stessa maniera per gli algoritmi informatici: non esiste il migliore in senso assoluto, ma il migliore rispetto a qualcosa. Poiché molto spesso quello che conta è che un programma sia veloce, allora un algoritmo è migliore di un’altro se impiega meno tempo ad essere eseguito.

Purtroppo però il concetto di tempo non è così facile da formalizzare, soprattutto è difficile ripetere un esperiemento due volte nelle stesse identiche condizioni per verificare se un algoritmo è davvero più veloce di un altro. Ecco quindi che si usa un modo molto più oggettivo di misuarazioni delle prestazioni, si contano semplicemente il numero delle operazioni fatte da ciascun algoritmo per ottenere il risultato, nel nostro caso (la ricerca del libro) quello che conta è il numero di titoli esaminati prima di trovare il libro in questione.

Possibili soluzioni

Verifichiamo allora la prima soluzione che ci viene in mente: partire dal primo libro e scorrerli via via tutti fin quando non lo troviamo. Soluzione semplice semplice e probabilmente quella più utilizzata nella pratica.

In questo caso quanti libri dovremo guardare prima di trovare il nostro libro? Beh dipende ovviamente da quanti libri abbiamo e dalla posizione occupata dal libro! Possiamo dire senza perdere di generalità che se abbiamo n libri nello scaffale, il numero di libri esaminati andrà da 1 (se sto cercando proprio il primo libro) fino a n+1 nel caso in cui il libro non ci sia nello scaffale.

Incuriositi dal +1 ? Se il libro cercato fosse l’ultimo dello scaffale ne avremmo esaminato n, mentre se non c’è dobbiamo fare un ultimo check per accorgerci effettivamente che quello era l’utlimo libro 😉

In media quindi un’operazione di ricerca con questo approccio verificherà n/2 libri, possiamo fare di meglio?

Certo che possiamo fare di meglio, anzi molto meglio! In fondo nel nostro primo approccio non abbiamo sfruttato un aspetto molto importante, il fatto che i libri sono ordinati in ordine alfabetico!

Allora proviamo a seguire il metodo della ricerca binaria eguendo queste istruzioni:

1. Prendiamo in considerazione l’interno scaffale.
2. Esaminiamo il libro esattamente a metà dell’insieme in considerazione.
3. Se il libro cercato è lessicograficamente maggiore di quello esaminato, consideriamo i libri nella seconda metà e passiamo al punto 6.
4. Se il libro cercato è lessicograficamente minore di quello esaminato, consideriamo i libri nella prima metà e passiamo al punto 6.
5. Se il libro esaminato è quello cercato terminiamo l’algoritmo.
6. Se l’insieme considerato contiene dei libri torniamo al punto 2
7. Se l’insieme considerato non contiene libri terminiamo l’algoritmo con ‘libro non trovato’.

Questo algoritmo, più furbo della ricerca sequenziale permette un notevole risparmio di confronti, infatti ogni volta che esaminiamo un libro la successiva analisi la facciamo solo su metà dell’insieme quindi il numero di confronti va da 1 (se il libro cercato è il primo esaminato) fino al massimo di log2(n) quindi in media (log2(n) / 2 ) !!!

Se la formula non vi provoca l’effetto “wow” proviamo a fare un esempio: nella biblioteca del congresso sono presenti secondo wikipedia 128milioni di documenti. Se supponessimo di averli già ordinati in ordine alfabetico e dovessimo cercarne uno con il primo algoritmo impiegheremmo più di due anni lavorando 24h su 24 analizzando un documento al secondo, mentre invece con il secondo algorimo impiegheremmo solo 13 secondi… un bel po’ di risparmio, non credete?

Il nostro esempio

In rete si trovano molte implementazioni della ricerca binaria, io preferisco la versione ricorsiva.

Vi propongo qui un piccolo programma che genera un milione di interi random (crescenti) e poi esegue la ricerca di un valore all’interno di questo array, effettuando la ricerca sia con l’approccio lineare che con quello binario. Al termine vegono stampate le prestazioni di ciascun algoritmo.

Il codice delle due ricerche è stato modificato aggiungendo un parametro utile per calcolare il numero di operazioni eseguite dall’algoritmo, nella pratica questo ultimo parametro non è necessario.

Ricordo per chi non ci avesse mai fatto caso, che le funzioni in c restituiscono sempre e solo un unico valore. Quando si ha la necessità di restituire più valori si può ricorrere a due tecniche, la prima è quella di restituire un puntatore ad una struttura, la seconda tecnica è quella di passare dei parametri appositi alla funzione che vengono modificati dal corpo della funzione stessa.

#include 
#include 
#include 

int indexof(int target, int *array, int left, int right, int *num_operazioni);
int indexof_linear(int target, int *array, int size, int *num_operazioni);

int main(int argc, char *argv[]) {
        
        int *array;
        int num_operazioni = 0;
        int num_elementi = 1000000;
        //Questo codice serve per modificare il seed del generatore di numeri random.
        srand(time(NULL));
        
        
        //Creo un array di taglia num_elementi e lo popolo con elementi random crescenti.
        array = calloc(num_elementi, sizeof(int));
        int lastValue = 0;
        for (int i = 0; i < num_elementi; i++) {
                array[i] = lastValue + (rand() % 5 + 1);
                lastValue = array[i];
        }
        
        //Genero randon un elemento da ricercare nel range dell'array.
        int elemento_ricercato = rand() % lastValue + 1;
        
        
        printf("Elemento ricercato: %d\n", elemento_ricercato);
        //Avvio la ricerca con la ricerca binaria.
        int k = indexof(elemento_ricercato,array,0,num_elementi, &num_operazioni);
        if (k > 0) {
                printf("Trovato in posizione: %d, dopo %d operazioni\n", k, num_operazioni);
        }
        else {
                printf("Elemento non presente. Effettuate %d operazioni\n", num_operazioni);
        }
        
        //Azzero i contatori per eseguire lo stesso programma pcon l'algoritmo lineare.
        num_operazioni = 0;
        k = -1;
        k = indexof_linear(elemento_ricercato,array,num_elementi, &num_operazioni);
        if (k > 0) {
                printf("Trovato in posizione: %d, dopo %d operazioni\n", k, num_operazioni);
        }
        else {
                printf("Elemento non presente. Effettuate %d operazioni\n", num_operazioni);
        }
}


int indexof(int target, int *array, int left, int right, int *num_operazioni) {
        //Se ho esaurito gli elementi vuol dire che non ho trovato quello che cerco.
        // restituisco quindi un valore simbolico, -1 in questo caso.
        if (left > right)
                return -1;
                
        //m è l'indice dell'elemento centrale
        int m = (left + right) / 2;
        
        //ho trovato l'emento
        if (target == array[m]) {
                return m;
        } else if (target < m[array]) {  //Se il mio target è minore dell'elemento a metà prendo in considerazione la prima metà dell'insieme
                (*num_operazioni)++;
                return indexof(target, array, left, m - 1, num_operazioni);
        } else { //Se non è nessuno dei due casi precedenti allora deve essere maggiore.
                (*num_operazioni)++;
                return  indexof(target, array, m+1, right, num_operazioni);
        }
}


int indexof_linear(int target, int *array, int size, int *num_operazioni) {
        int i = 0;
        while (i <  size ) {
                if (array[i] == target) {
                        return i;
                }
                i++;
                (*num_operazioni)++;
        }
        return -1;
}

Il codice è commentato, spero quindi che sia comprensibile, posto qui un paio di risultati interessanti:

Elemento ricercato: 976482
Elemento non presente. Effettuate 20 operazioni
Elemento non presente. Effettuate 1000000 operazioni

Elemento ricercato: 35616
Trovato in posizione: 11770, dopo 16 operazioni
Trovato in posizione: 11770, dopo 11770 operazioni

Non c'è che dire... la ricerca binaria fa proprio il suo dovere!

Alla prossima!
ignazioc