Ricerca binaria

2.1 Definizione della ricerca binaria e i suoi concetti chiave

Ricerca binaria — è un algoritmo di ricerca di un elemento in un array ordinato, che funziona dividendo l'array a metà. Questo algoritmo è significativamente più efficiente della ricerca lineare per array grandi, poiché riduce il numero di controlli dividendo l'array in due parti a ogni iterazione.

Concetti chiave:

• Array ordinato: La ricerca binaria funziona solo su array ordinati.
• Divisione a metà: L'algoritmo confronta l'elemento cercato con l'elemento al centro dell'array.
• Divisione ricorsiva o iterativa: Se l'elemento cercato è minore del medio, la ricerca continua nella metà sinistra dell'array, altrimenti nella destra.
• Condizione di termine: La ricerca si conclude quando l'elemento è trovato o l'intervallo di ricerca diventa vuoto.

Importante! Per la ricerca binaria serve un array ordinato.

Per funzionare correttamente, gli input per la ricerca binaria devono essere ordinati in modo crescente. Questo è il requisito principale e unico, poiché l'algoritmo si basa sul fatto che gli elementi dell'array sono ordinati. Grazie a questo, può escludere in modo efficiente metà degli elementi a ogni passo di ricerca.

Esempio di array ordinato:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Implementazione passo per passo della ricerca binaria

Come funziona la ricerca binaria:

1. Inizializzazione: Impostare i limiti iniziali di ricerca (limiti sinistra e destra dell'array).
2. Scelta dell'elemento medio: Trovare l'indice dell'elemento medio dell'array.
3. Confronto: Confrontare l'elemento medio con il valore cercato.
4. Aggiornamento dei limiti:
   1. Se l'elemento medio è uguale al valore cercato, restituire il suo indice.
   2. Se il valore cercato è minore dell'elemento medio, aggiornare il limite destro di ricerca.
   3. Se è maggiore, aggiornare il limite sinistro.
5. Ripetizione: Ripetere i passi 2-4 fino a trovare l'elemento o finché il limite sinistro non supera il limite destro.

Algoritmo passo per passo:

1. Inizializzazione: Impostare left a 0 e right a len(arr) - 1.
2. Calcolare l'elemento medio: mid = (left + right) // 2
3. Confrontare con l'elemento obiettivo:
   1. Se arr[mid] == target, restituire mid
   2. Se arr[mid] < target, aggiornare left = mid + 1
   3. Se arr[mid] > target, aggiornare right = mid - 1
4. Ripetere: Tornare al passo 2 finché left <= right
5. Se l'elemento non è trovato: Restituire -1

Implementazione iterativa della ricerca binaria in Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Esempio di utilizzo:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Elemento {target} trovato all'indice {result}")  # Output: Elemento 7 trovato all'indice 3

2.3 Complessità temporale della ricerca binaria O(log n)

La ricerca binaria ha una complessità temporale di O(log n), dove n è il numero di elementi nell'array. Questo significa che a ogni passaggio l'algoritmo dimezza il numero di elementi, accelerando significativamente la ricerca rispetto alla ricerca lineare, che ha una complessità temporale di O(n).

Analisi della complessità temporale:

• Miglior caso (Best case): Elemento trovato al primo passaggio, O(1).
• Caso medio (Average case): O(log n).
• Peggior caso (Worst case): Elemento trovato all'ultimo passaggio o assente, O(log n).

Esempio per l'analisi della complessità temporale:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Elemento {target} trovato all'indice {index}")  # Output: Elemento 7 trovato all'indice 3

# L'algoritmo ha fatto 3 passi (logaritmo di 7 elementi) per trovare l'elemento, 
# che corrisponde a O(log n)

Rappresentazione grafica della complessità:

Immagina un array di 16 elementi.

Supponiamo che stiamo cercando l'elemento 15, allora i passi saranno:

Primo passo. Controlla l'elemento medio (8 elementi restano).

Secondo passo. Controlla l'elemento medio nella metà rimanente (4 elementi restano).

Terzo passo. Controlla l'elemento medio nella metà rimanente (2 elementi restano).

Quarto passo. Controlla l'ultimo elemento (1 elemento resta).

Di conseguenza, l'algoritmo eseguirà 4 passi per un array di 16 elementi, che corrisponde al logaritmo in base 2 di 16, cioè, log2(16) = 4. Questa è la complessità logaritmica O(log n).