di Sergio Mauri

L’algoritmo di ricerca binaria è un algoritmo efficiente per trovare un elemento in un elenco ordinato. Si basa sul principio della divisione e conquista e funziona come segue:

1. Inizializzazione: l’array in cui eseguire la ricerca deve essere ordinato in modo non decrescente per garantire l’efficacia dell’algoritmo.
2. Definizione dei puntatori: si definisce un puntatore iniziale all’inizio dell’array chiamato low e un puntatore finale alla fine dell’array chiamato high.
3. Calcolo del punto medio: si calcola l’indice medio dell’array come mid=low+high/2​.
4. Confronto con l’elemento cercato:
   • Se l’elemento nell’indice medio è uguale all’elemento cercato, l’elemento è stato trovato e l’algoritmo restituisce l’indice medio.
   • Se l’elemento nell’indice medio è maggiore dell’elemento cercato, si aggiorna il puntatore high a mid - 1 e si continua la ricerca nella metà sinistra dell’array.
   • Se l’elemento nell’indice medio è minore dell’elemento cercato, si aggiorna il puntatore low a mid + 1 e si continua la ricerca nella metà destra dell’array.
5. Ripetizione del processo: Si ripetono i passaggi 3 e 4 fino a quando l’elemento cercato viene trovato o fino a quando low supera high. In quest’ultimo caso, l’elemento non è presente nell’array e la ricerca binaria restituisce un valore convenzionale (ad esempio -1).

La complessità dell’algoritmo di ricerca binaria è O(log n), dove n è la dimensione dell’array. Ciò significa che l’algoritmo è in grado di trovare un elemento in un grande insieme di dati in modo efficiente, poiché riduce il numero di confronti richiesti per trovare l’elemento desiderato.