Come funziona l'algoritmo di ricerca binaria?

La ricerca binaria funziona analizzando un array ordinato, dividendo successivamente l'intervallo di ricerca a metà.

1. Inizializzazione: Si definiscono il limite sinistro e destro dell'intervallo di ricerca (solitamente l'inizio e la fine dell'array).
2. Confronto: Si calcola l'indice del mezzo dell'intervallo. Il valore in quell'indice viene confrontato con l'elemento cercato.
3. Riduzione dell'intervallo:
   • Se il valore al centro corrisponde a quello cercato, l'elemento è stato trovato.
   • Se il valore al centro è maggiore di quello cercato, la ricerca continua nella metà sinistra dell'intervallo. Il limite destro si sposta a mezzo - 1.
   • Se il valore al centro è minore di quello cercato, la ricerca continua nella metà destra dell'intervallo. Il limite sinistro si sposta a mezzo + 1.
4. Ripetizione: I passaggi 2 e 3 vengono ripetuti fino a trovare l'elemento o l'intervallo di ricerca diventa vuoto.

La complessità dell'algoritmo è O(log n), molto più efficiente della ricerca lineare per array di grandi dimensioni.

Esempio di implementazione in Python:

def binary_search(arr, target):
    """
    Implementazione della ricerca binaria.
    Prende un array ordinato e il valore cercato.
    Restituisce l'indice dell'elemento o -1 se non trovato.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Calcolo dell'indice medio
        mid_val = arr[mid]      # Ottieni il valore al centro

        if mid_val == target:
            return mid  # Elemento trovato
        elif mid_val < target:
            left = mid + 1  # Ricerca a destra
        else: # mid_val > target
            right = mid - 1 # Ricerca a sinistra

    return -1 # Elemento non trovato