Pattern: Binary Search

Il pattern Binary Search permette di trovare rapidamente un elemento in una sequenza ordinata riducendo ogni volta lo spazio di ricerca a metà. È uno degli approcci più efficienti per interrogare array o intervalli numerici già ordinati.

🚀 Quando usarlo

Usa la ricerca binaria quando:

• L'array è già ordinato o puoi ordinarlo prima di cercare
• Devi individuare la presenza o la posizione esatta di un valore
• Vuoi cercare il punto di transizione tra due condizioni (ad es. il primo elemento maggiore o uguale a una soglia)

🧰 Varianti principali

Variante	Descrizione
Iterativa	Utilizza un ciclo while senza ricorsione
Ricorsiva	Chiama la funzione su metà dell'intervallo a ogni passo
Bound search	Modifica della ricerca per ottenere l'indice di inizio o fine di un intervallo

✏️ Esempio classico: Ricerca in un array ordinato

Leetcode 704. Binary Search

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

✅ Complessità:

• Tempo: O(log n)
• Spazio: O(1) nella versione iterativa

🧩 Problemi comuni

Nome	Difficoltà	Pattern	Link
Binary Search	Easy	Iterativa	Leetcode #704
First Bad Version	Easy	Ricorsiva	Leetcode #278
Search Insert Position	Easy	Bound search	Leetcode #35
Find Minimum in Rotated Sorted Array	Medium	Modificata	Leetcode #153
Search a 2D Matrix	Medium	Iterativa	Leetcode #74

💡 Consigli utili

• Controlla sempre che la sequenza sia ordinata prima di applicare l'algoritmo
• Calcola l'indice medio come left + (right - left) // 2 per evitare overflow
• Le versioni che trovano il limite inferiore o superiore sono utili per contare elementi o gestire intervalli

📚 Continua con

👉 Breadth-First Search →