Quale algoritmo ha una complessità logaritmica O(log n)?

L'algoritmo di ricerca binaria (o dicotomica) ha una complessità temporale logaritmica O(log n).

Principio di funzionamento della ricerca binaria:

1. Richiede un array (o lista) ordinato.
2. Ad ogni passo, confronta l’elemento cercato con l’elemento al centro dell’intervallo di ricerca corrente.
3. Se gli elementi coincidono, la ricerca termina.
4. Se l’elemento cercato è minore del centro, la ricerca continua nella metà sinistra dell’intervallo.
5. Se l’elemento cercato è maggiore del centro, la ricerca continua nella metà destra dell’intervallo.
6. L’intervallo di ricerca si riduce della metà ad ogni passo.

Esempio di implementazione in Python:

# Funzione di ricerca binaria
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Elemento trovato, ritorna l’indice
        elif mid_val < target:
            low = mid + 1  # Ignora la metà sinistra
        else:
            high = mid - 1  # Ignora la metà destra

    return -1  # Elemento non trovato

# Esempio di utilizzo
# lista_ordinata = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# valore_cercato = 23
# risultato = binary_search(lista_ordinata, valore_cercato)
# if risultato != -1:
#     print(f"Elemento trovato all’indice: {risultato}")
# else:
#     print("Elemento non trovato")

La complessità logaritmica è dovuta al fatto che il numero di operazioni è proporzionale al logaritmo della dimensione dei dati di input (n), poiché ad ogni passo, lo spazio di ricerca si riduce della metà.