Ricerca binaria ricorsiva

3.1 Principio di funzionamento della ricerca binaria ricorsiva

La ricerca binaria è un algoritmo per trovare un elemento in un array ordinato che funziona secondo il principio "divide et impera". Confronta l'elemento cercato con l'elemento al centro dell'array e decide in quale metà dell'array cercare ulteriormente. La ricerca binaria ricorsiva ripete questo processo, chiamando se stessa con i confini aggiornati dell'array.

Passi dell'algoritmo:

1. Confrontiamo l'elemento cercato con l'elemento al centro dell'array.
2. Se l'elemento al centro coincide con quello cercato, restituiamo il suo indice.
3. Se l'elemento cercato è minore, ripetiamo la ricerca nella metà sinistra dell'array.
4. Se l'elemento cercato è maggiore, ripetiamo la ricerca nella metà destra dell'array.
5. Ripetiamo il processo finché non troviamo l'elemento o esauriamo l'array.

Implementazione della ricerca binaria ricorsiva

Esempio in Python:

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # Caso base: elemento non trovato
            
    mid = (left + right) // 2  # Troviamo il centro dell'array
            
    if arr[mid] == target:
        return mid  # Caso base: elemento trovato
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)  # Cerchiamo nella metà destra
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # Cerchiamo nella metà sinistra
        
# Esempio d'uso:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Elemento trovato alla posizione: {result}")  # Stampa: Elemento trovato alla posizione: 6
        

3.2 Confronto con la ricerca binaria iterativa

Ricerca binaria iterativa:

def binary_search_iterative(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  # Elemento non trovato
        
# Esempio d'uso:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_iterative(arr, target)
print(f"Elemento trovato alla posizione: {result}")  # Stampa: Elemento trovato alla posizione: 6
        

Confronto:

Semplicità di implementazione:

• L'algoritmo ricorsivo è solitamente più semplice e corto, ma richiede la comprensione delle chiamate ricorsive.
• L'algoritmo iterativo utilizza un ciclo, il che potrebbe essere più facile per i programmatori principianti.

Memoria:

• L'algoritmo ricorsivo utilizza lo stack delle chiamate, il che può portare a un aumento dell'utilizzo della memoria con array grandi.
• L'algoritmo iterativo utilizza una quantità costante di memoria, il che lo rende più efficiente dal punto di vista dell'uso della memoria.

Prestazioni:

• Entrambi gli algoritmi hanno una complessità temporale di O(log n).
• L'algoritmo ricorsivo può essere più lento a causa degli overhead delle chiamate ricorsive, specialmente se la profondità della ricorsione è grande.

3.3 Esempi di problemi per la ricerca binaria ricorsiva

La ricerca binaria ricorsiva è un algoritmo potente che aiuta a trovare rapidamente elementi in array ordinati. Si basa sul principio del "divide et impera" e utilizza la ricorsione per dividere il problema in sotto-problemi più piccoli.

Il confronto tra approcci ricorsivi e iterativi mostra che ognuno ha i suoi vantaggi e svantaggi a seconda del problema specifico. Comprendere questi algoritmi e il loro utilizzo permette di risolvere efficacemente problemi di ricerca in programmazione.

Ad esempio, tali:

Ricerca di un elemento in un array ordinato:

Ricerca di un elemento specifico in un array di numeri, ad esempio, valutazione dei test, ricerca in un database tramite chiavi ordinate e così via.

Verifica della presenza di un elemento:

Verifica se un determinato valore è presente in un elenco di utenti consentiti, identificatori e così via.

Ricerca del valore più vicino:

Ricerca di un elemento il più vicino possibile a un valore dato nell'array, ad esempio, nella ricerca del negozio più vicino, della stazione e così via.

Ottimizzazione:

Risoluzione di problemi che richiedono la ricerca di un valore ottimale in un array ordinato, ad esempio, trovare il punto di minimo o massimo in funzioni.