Ciao a tutti da alcuni giorni mi sono cementato nel fantastico mondo del codice binario e ho scoperto delle cose molto interessanti, perciò ho voluto scrivervi un articolo su di esso.

Il codice binario è un algoritmo di ricerca che consente di velocizzare notevolmente i ritrovamento degli oggetti.
La ricerca binaria a sua volta è una tecnica di individuazione di elementi di una lista ordinata, capace di fare molto meglio di una normale ricerca lineare (Es. scorro il file finchè non lo trovo). E' requisito essenziale che la lista sia ordinata.

Il tempo medio di una ricerca lineare, dal primo all'ultimo elemento, è pari al tempo necessario per esaminare metà degli elementi nella lista.

La ricerca binaria puo fare assai meglio e prende il suo nome dal fatto che lo spazio da ricercare viene progressivamente dimezzato e continua a restringersi molto piu velocemente che in una ricerca lineare fino a quando non si arriva a bersaglio.

:: Divide et impera (scusate se il mio latino non è dei migliori) ::
(In latino dividi e comanda). Ecco come funziona un algoritmo di ricerca binaria:

1.Ci si posiziona a metà della lista (che ricordo per l'ultima volta deve essere ordinata)
2.Confrontiamo la chiave di ricerca con l'elemento presente in quella posizione.
3.Se coincidono abbiamo finito!
4.Se la chiave di ricerca ha valore inferiore a quello dell'elemento su cui ci troviamo, vuol dire che l'elemento ricercato, se è presente, sta nella metà inferiore della lista; spezziamo la lista in 2 e ripartiamo dal passo 1, considerando solo la metà inferiore della lista.
5.Analogamente, se la chiave di ricerca ha valore maggiore, spezziamo la lista in 2 e ripartiamo dal passo 1, solo però considerando la metà superiore della lista.

Un esempio concreto. Vogliamo la lettera K nella lista ADFHIKLMP (si, noi la vediamo subito, ma il computer no!).

Confrontiamo la chiave di ricerca (la lettera K) con la posizione di metà della lista, che è la lettera I:
(Ecco un'immagine fatta da me in ASCII)
----------------------
| 0 1 2 3 *4* 5 6 7 8 |
| A D F H *I* K L M P |
----------------------

K ha un valore mggiore di I. Quindi spezziamo la lista in 2 e ripartiamo considerando la metà superiore della lista. Contrariamente al senso comune, la metà superiore della lista è quella dove i valori sono maggiori e quindi è la 2 metà della lista, non l'inizio come lo vediamo noi.

Quindi:

----------------------------
| 0 1 2 3 4 5 6 7 8 |
| +---------+ |
| A D F H I |K L M P| |
| +---------+ |
----------------------------

Questa metà della lista è composta da un numero pari di elementi. Come facciamo a poszionarci esattamente in mezzo? Non è un problema. Se la lista è pari possiamo scegliere arbitrariamente di posizionarci mezzo passo prima o mezzo passo dopo e cioè, nel nostro esempio, su L o su M. Diciamo L:

----------------------------
| 0 1 2 3 4 5 6 7 8 |
| +----------+|
| A D F H I |K *L* M P||
| +----------+|
----------------------------



K ha un valore minore di L. Dividiamo in 2 la lista e partiamo dalla metà inferiore. Questa metà è composta da un solo elemento, la lettera K. Coincide con la chiave di ricerca K. Abbiamo trovato. Ci abbiamo messo 3 tentativi. Con la ricerca lineare, partendo dalla A e proseguendo, ce ne avremmo messi 6. Certo, se avessimo dovuto cercare la lettera A con una ricerca lineare, ci avremmo messo un solo tentativo, contro "quanti" su una ricerca binaria.
Ma la ricerca lineare da buoni risultati solo in casi particolari. Mediamente, la ricera binaria è superiore e lo diventa sempre piu con l'aumentare della lunghezza della lista.