{"id":9554,"date":"2012-09-24T14:41:11","date_gmt":"2012-09-24T12:41:11","guid":{"rendered":"http:\/\/www.devapp.it\/wordpress\/?p=9554"},"modified":"2012-09-24T14:41:11","modified_gmt":"2012-09-24T12:41:11","slug":"19-un-esempio-classico-la-ricerca-binaria","status":"publish","type":"post","link":"https:\/\/www.devapp.it\/wordpress\/19-un-esempio-classico-la-ricerca-binaria\/","title":{"rendered":"19. Un esempio classico: La ricerca binaria"},"content":{"rendered":"

\"corso-completo-c-19-la-ricerca-binaria\"<\/a> 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 \u00e8 semplicissima e la soluzione \u00e8 apprezzabile da tutti, anche se non si ha alcun background tecnico. Ma partiamo dall’inizio e scopriamo di cosa si tratta.<\/p>\n

La definizione del problema<\/h4>\n

La definizione pu\u00f2 essere data anche senza dover usare termini informatici, infatti, il problema della ricerca binaria (o dicotomica) \u00e8 quello di trovare un elemento all’interno di una collezione ordinata di elementi omogenei.<\/p>\n

Supponiamo di avere uno scaffale pieno di libri ordinati rigorosamente in ordine alfabetico, e di doverne ricercare uno in particolare: qual \u00e8 secondo voi l’approccio migliore?<\/p>\n

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

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

Purtroppo per\u00f2 il concetto di tempo non \u00e8 cos\u00ec facile da formalizzare, soprattutto \u00e8 difficile ripetere un esperiemento due volte nelle stesse identiche condizioni per verificare se un algoritmo \u00e8 davvero pi\u00f9 veloce di un altro. Ecco quindi che si usa un modo molto pi\u00f9 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 \u00e8 il numero di titoli esaminati prima di trovare il libro in questione.<\/p>\n

Possibili soluzioni<\/h4>\n

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\u00f9 utilizzata nella pratica.<\/p>\n

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\u00e0 che se abbiamo n libri nello scaffale, il numero di libri esaminati andr\u00e0 da 1 (se sto cercando proprio il primo libro) fino a n+1 nel caso in cui il libro non ci sia nello scaffale.<\/p>\n

Incuriositi dal +1 ? Se il libro cercato fosse l’ultimo dello scaffale ne avremmo esaminato n, mentre se non c’\u00e8 dobbiamo fare un ultimo check per accorgerci effettivamente che quello era l’utlimo libro \ud83d\ude09<\/p>\n

In media quindi un’operazione di ricerca con questo approccio verificher\u00e0 n\/2 libri, possiamo fare di meglio?<\/p>\n

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!<\/p>\n

Allora proviamo a seguire il metodo della ricerca binaria eguendo queste istruzioni:<\/p>\n

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

    Questo algoritmo, pi\u00f9 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\u00e0 dell’insieme quindi il numero di confronti va da 1 (se il libro cercato \u00e8 il primo esaminato) fino al massimo di log2(n) quindi in media (log2(n) \/ 2 ) !!!<\/p>\n

    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\u00e0 ordinati in ordine alfabetico e dovessimo cercarne uno con il primo algoritmo impiegheremmo pi\u00f9 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?<\/p>\n

    Il nostro esempio<\/h4>\n

    In rete si trovano molte implementazioni della ricerca binaria, io preferisco la versione ricorsiva.<\/p>\n

    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.<\/p>\n

    Il codice delle due ricerche \u00e8 stato modificato aggiungendo un parametro utile per calcolare il numero di operazioni eseguite dall’algoritmo, nella pratica questo ultimo parametro non \u00e8 necessario.<\/p>\n

    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\u00e0 di restituire pi\u00f9 valori si pu\u00f2 ricorrere a due tecniche, la prima \u00e8 quella di restituire un puntatore ad una struttura, la seconda tecnica \u00e8 quella di passare dei parametri appositi alla funzione che vengono modificati dal corpo della funzione stessa.<\/p>\n

    \r\n#include \r\n#include \r\n#include \r\n\r\nint indexof(int target, int *array, int left, int right, int *num_operazioni);\r\nint indexof_linear(int target, int *array, int size, int *num_operazioni);\r\n\r\nint main(int argc, char *argv[]) {\r\n        \r\n        int *array;\r\n        int num_operazioni = 0;\r\n        int num_elementi = 1000000;\r\n        \/\/Questo codice serve per modificare il seed del generatore di numeri random.\r\n        srand(time(NULL));\r\n        \r\n        \r\n        \/\/Creo un array di taglia num_elementi e lo popolo con elementi random crescenti.\r\n        array = calloc(num_elementi, sizeof(int));\r\n        int lastValue = 0;\r\n        for (int i = 0; i < num_elementi; i++) {\r\n                array[i] = lastValue + (rand() % 5 + 1);\r\n                lastValue = array[i];\r\n        }\r\n        \r\n        \/\/Genero randon un elemento da ricercare nel range dell'array.\r\n        int elemento_ricercato = rand() % lastValue + 1;\r\n        \r\n        \r\n        printf(\"Elemento ricercato: %d\\n\", elemento_ricercato);\r\n        \/\/Avvio la ricerca con la ricerca binaria.\r\n        int k = indexof(elemento_ricercato,array,0,num_elementi, &num_operazioni);\r\n        if (k > 0) {\r\n                printf(\"Trovato in posizione: %d, dopo %d operazioni\\n\", k, num_operazioni);\r\n        }\r\n        else {\r\n                printf(\"Elemento non presente. Effettuate %d operazioni\\n\", num_operazioni);\r\n        }\r\n        \r\n        \/\/Azzero i contatori per eseguire lo stesso programma pcon l'algoritmo lineare.\r\n        num_operazioni = 0;\r\n        k = -1;\r\n        k = indexof_linear(elemento_ricercato,array,num_elementi, &num_operazioni);\r\n        if (k > 0) {\r\n                printf(\"Trovato in posizione: %d, dopo %d operazioni\\n\", k, num_operazioni);\r\n        }\r\n        else {\r\n                printf(\"Elemento non presente. Effettuate %d operazioni\\n\", num_operazioni);\r\n        }\r\n}\r\n\r\n\r\nint indexof(int target, int *array, int left, int right, int *num_operazioni) {\r\n        \/\/Se ho esaurito gli elementi vuol dire che non ho trovato quello che cerco.\r\n        \/\/ restituisco quindi un valore simbolico, -1 in questo caso.\r\n        if (left > right)\r\n                return -1;\r\n                \r\n        \/\/m \u00e8 l'indice dell'elemento centrale\r\n        int m = (left + right) \/ 2;\r\n        \r\n        \/\/ho trovato l'emento\r\n        if (target == array[m]) {\r\n                return m;\r\n        } else if (target < m[array]) {  \/\/Se il mio target \u00e8 minore dell'elemento a met\u00e0 prendo in considerazione la prima met\u00e0 dell'insieme\r\n                (*num_operazioni)++;\r\n                return indexof(target, array, left, m - 1, num_operazioni);\r\n        } else { \/\/Se non \u00e8 nessuno dei due casi precedenti allora deve essere maggiore.\r\n                (*num_operazioni)++;\r\n                return  indexof(target, array, m+1, right, num_operazioni);\r\n        }\r\n}\r\n\r\n\r\nint indexof_linear(int target, int *array, int size, int *num_operazioni) {\r\n        int i = 0;\r\n        while (i <  size ) {\r\n                if (array[i] == target) {\r\n                        return i;\r\n                }\r\n                i++;\r\n                (*num_operazioni)++;\r\n        }\r\n        return -1;\r\n}\r\n<\/pre>\n
    Il codice \u00e8 commentato, spero quindi che sia comprensibile, posto qui un paio di risultati interessanti:<\/p>\n
    \r\nElemento ricercato: 976482\r\nElemento non presente. Effettuate 20 operazioni\r\nElemento non presente. Effettuate 1000000 operazioni\r\n\r\nElemento ricercato: 35616\r\nTrovato in posizione: 11770, dopo 16 operazioni\r\nTrovato in posizione: 11770, dopo 11770 operazioni\r\n<\/pre>\n
    Non c'\u00e8 che dire... la ricerca binaria fa proprio il suo dovere!<\/p>\n
    Alla prossima!
    \nignazioc<\/p>\n","protected":false},"excerpt":{"rendered":"
    Probabilmente tutti quelli che hanno studiato programmazione a scuola si sono trovati, chi prima chi poi (se…<\/p>\n","protected":false},"author":53,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[569],"tags":[589,1203,592,1202],"class_list":["post-9554","post","type-post","status-publish","format-standard","hentry","category-corso-completo-di-c","tag-corso-di-programmazione-in-c","tag-esempi-codie-c","tag-programmare-in-c","tag-ricerca-binaria-in-c"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/9554","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/users\/53"}],"replies":[{"embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/comments?post=9554"}],"version-history":[{"count":26,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/9554\/revisions"}],"predecessor-version":[{"id":9587,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/9554\/revisions\/9587"}],"wp:attachment":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/media?parent=9554"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/categories?post=9554"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/tags?post=9554"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}