Corso ALGORITMI PER LA PROGRAMMAZIONE: Lezione 8 Algoritmi di ricerca

8-Algoritmi di ricerca: Questi algoritmi sono progettati per trovare un elemento specifico all'interno di una sequenza ordinata o non ordinata. Alcuni esempi di algoritmi di ricerca includono:

8.1- Ricerca lineare: Esamina sequenzialmente ogni elemento dell'array fino a trovare l'elemento desiderato o fino a esaurire tutti gli elementi.

Ecco un esempio di implementazione di un algoritmo di ricerca lineare in Python:

python

Copy code

def ricerca_lineare(arr, target):

    for i in range(len(arr)):

        if arr[i] == target:

            return i  # Restituisce l'indice se l'elemento è stato trovato

    return -1  # Restituisce -1 se l'elemento non è presente nell'array

# Esempio di utilizzo:

array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

elemento = 23

risultato = ricerca_lineare(array, elemento)

if risultato != -1:

    print(f"L'elemento {elemento} si trova all'indice {risultato}.")

else:

    print(f"L'elemento {elemento} non è presente nell'array.")

Spiegazione dell'algoritmo:

La funzione ricerca_lineare prende in input un array arr e l'elemento target che si desidera trovare.

Utilizza un ciclo for per scorrere tutti gli elementi dell'array arr.

Per ogni elemento, verifica se è uguale all'elemento target che si sta cercando.

Se trova l'elemento desiderato, restituisce l'indice in cui è stato trovato.

Se l'algoritmo esamina tutti gli elementi senza trovare l'elemento target, restituisce -1 per indicare che l'elemento non è presente nell'array.

L'algoritmo di ricerca lineare esamina sequenzialmente ogni elemento dell'array fino a trovare l'elemento desiderato o fino a esaurire tutti gli elementi. Se l'array è grande o l'elemento desiderato si trova verso la fine, la ricerca potrebbe richiedere un numero considerevole di iterazioni. La complessità temporale nel caso peggiore per la ricerca lineare è 

O(n), dove n è la lunghezza dell'array, poiché l'algoritmo deve potenzialmente esaminare ogni elemento dell'array.

8.2- Ricerca binaria: Si applica solo a sequenze ordinate e funziona dividendo ripetutamente l'intervallo di ricerca a metà finché l'elemento desiderato non viene trovato o finché non viene stabilito che l'elemento non è presente.

Ecco un esempio di implementazione di un algoritmo di ricerca binaria in Python:

python

Copy code

def ricerca_binaria(arr, target):

    left = 0

    right = len(arr) - 1

    while left <= right:

        mid = (left + right) // 2  # Trova l'indice medio dell'intervallo

        # Controlla se l'elemento medio è uguale al target

        if arr[mid] == target:

            return mid  # Restituisce l'indice se l'elemento è stato trovato

        elif arr[mid] < target:

            left = mid + 1  # Ricerca nella metà destra dell'intervallo

        else:

            right = mid - 1  # Ricerca nella metà sinistra dell'intervallo

    return -1  # Restituisce -1 se l'elemento non è presente nell'array

# Esempio di utilizzo:

array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

elemento = 23

risultato = ricerca_binaria(array, elemento)

if risultato != -1:

    print(f"L'elemento {elemento} si trova all'indice {risultato}.")

else:

    print(f"L'elemento {elemento} non è presente nell'array.")

Spiegazione dell'algoritmo:

La funzione ricerca_binaria prende in input un array arr ordinato e l'elemento target che si desidera trovare.

Inizializza due indici left e right per rappresentare l'intervallo di ricerca all'interno dell'array.

Finché left è minore o uguale a right, l'algoritmo esegue un ciclo.

Trova l'indice medio dell'intervallo usando l'operazione intera //.

Controlla se l'elemento al centro dell'intervallo è uguale al target. Se è uguale, restituisce l'indice in cui è stato trovato l'elemento.

Se l'elemento al centro è maggiore del target, si restringe l'intervallo di ricerca alla metà sinistra escludendo l'elemento al centro.

Se l'elemento al centro è minore del target, si restringe l'intervallo di ricerca alla metà destra escludendo l'elemento al centro.

Continua questo processo finché l'elemento desiderato non viene trovato o finché left supera right.

Se l'elemento non viene trovato, restituisce -1.

La ricerca binaria è efficiente su array ordinati poiché riduce l'intervallo di ricerca a metà ad ogni passaggio, risultando in una complessità temporale di 

O(logn), dove n è la lunghezza dell'array.

Altri algoritmi di ricerca specializzati: Esistono diverse varianti di algoritmi di ricerca ottimizzati per specifici contesti o tipi di dati.