A cosa serve l'algoritmo di ricerca binaria?

Per cercare efficacemente un elemento in un array ordinato.

L'essenza consiste nel confrontare il valore cercato con l'elemento al centro dell'intervallo di ricerca corrente. Se sono uguali, l'elemento è stato trovato. Se il valore cercato è minore, la ricerca si restringe alla metà sinistra; se è maggiore, alla metà destra. Il processo si ripete finché l'elemento non viene trovato o l'intervallo di ricerca diventa vuoto.

Vantaggio rispetto alla ricerca lineare è la complessità temporale logaritmica, O(log n), mentre quella lineare è O(n). Questo la rende molto più veloce per grandi array.

Applicazioni:

• Ricerca in dizionari e database (indici).
• Algoritmi di ordinamento (ad esempio, nel merge sort).
• Ricerca dell'elemento radice in un'equazione.
• Ricerca in strutture dati di tipo alberi B.