Esempi di problemi per la ricerca lineare e binaria

3.1 Problema di ricerca di un elemento in un array utilizzando la ricerca lineare

Problema: Dato un array di numeri. È necessario trovare l'indice di un numero dato utilizzando la ricerca lineare. Se il numero non viene trovato, restituire -1.

Esempio:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Esempio di utilizzo:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Elemento {target} trovato all'indice {result}")  # Uscita: Elemento 7 trovato all'indice 2

# Esempio di utilizzo per un elemento non presente nell'array:
target = 5
result = linear_search(arr, target)
print(f"Elemento {target} trovato all'indice {result}")  # Uscita: Elemento 5 trovato all'indice -1

Spiegazione:

• La funzione linear_search scorre ogni elemento dell'array arr e lo confronta con target.
• Se l'elemento viene trovato, restituisce il suo indice.
• Se tutti gli elementi sono stati controllati e il valore cercato non è stato trovato, la funzione restituisce -1.

Passaggi:

1. Array [4, 2, 7, 1, 9, 3] e valore cercato 7.
2. Inizio ricerca: confronto del primo elemento (4) con 7 — non corrisponde.
3. Passa al prossimo elemento (2) — non corrisponde.
4. Passa al prossimo elemento (7) — corrisponde.
5. Ritorna indice 2.

3.2 Problema di ricerca di un elemento in un array ordinato utilizzando la ricerca binaria

Problema: Dato un array ordinato di numeri. È necessario trovare l'indice di un numero dato utilizzando la ricerca binaria. Se il numero non viene trovato, restituire -1.

Esempio:

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}")  # Uscita: Elemento 7 trovato all'indice 3

# Esempio di utilizzo per un elemento non presente nell'array:
target = 6
result = binary_search(sorted_array, target)
print(f"Elemento {target} trovato all'indice {result}")  # Uscita: Elemento 6 trovato all'indice -1

Spiegazione:

• La funzione binary_search utilizza due puntatori (left e right) per tracciare i confini della ricerca nell'array arr.
• Ad ogni iterazione si trova l'elemento medio dell'array e lo si confronta con target.
• Se l'elemento medio è uguale a target, restituisce il suo indice.
• Se target è minore dell'elemento medio, la ricerca continua nella metà sinistra dell'array.
• Se target è maggiore dell'elemento medio, la ricerca continua nella metà destra dell'array.
• Se i confini si incrociano e l'elemento non viene trovato, si restituisce -1.

Passaggi:

1. Array ordinato [1, 3, 5, 7, 9, 11, 13] e valore cercato 7.
2. Confini iniziali della ricerca: left = 0, right = 6.
3. Trova l'elemento medio: mid = (0 + 6) // 2 = 3.
4. Confronta l'elemento medio (7) con target (7) — corrisponde.
5. Ritorna indice 3.

3.3 Confronto e scelta dell'algoritmo di ricerca adatto per diversi problemi

Confronto tra ricerca lineare e binaria:

Scelta dell'algoritmo adatto

Ricerca lineare:

• Utilizzata quando i dati non sono ordinati.
• Adatta per array o liste piccole.
• Usata quando il numero di elementi è ridotto e il tempo di esecuzione non è cruciale.

Ricerca binaria:

• Applicata quando i dati sono ordinati.
• Ideale per array grandi, dove la velocità di ricerca è importante.
• Efficace se è necessaria una ricerca frequente nello stesso insieme di dati (è possibile ordinare i dati in anticipo).

3.4 Esercizi pratici per consolidare il materiale

Esercizio 1: Ricerca lineare

Dato un array di numeri. Scrivi una funzione per cercare un numero dato utilizzando la ricerca lineare. La funzione deve restituire l'indice dell'elemento trovato o -1 se l'elemento non viene trovato.

Esempio:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Esempio di utilizzo:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Elemento {target} trovato all'indice {result}")  # Uscita: Elemento 7 trovato all'indice 2

# Test aggiuntivi:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Esercizio 2: Ricerca binaria

Dato un array ordinato di numeri. Scrivi una funzione per cercare un numero dato utilizzando la ricerca binaria. La funzione deve restituire l'indice dell'elemento trovato o -1 se l'elemento non viene trovato.

Esempio:

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}")  # Uscita: Elemento 7 trovato all'indice 3

# Test aggiuntivi:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Esercizio 3: Confronto tra ricerca lineare e binaria

Dato un array di numeri. Scrivi due funzioni per cercare un numero dato: una utilizzando la ricerca lineare, l'altra utilizzando la ricerca binaria. Confronta le prestazioni di entrambe le funzioni su array di grandi dimensioni.

Esempio:

import time
import random

# Ricerca lineare
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Ricerca binaria
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

# Generazione di un grande array
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Confronto delle prestazioni
start_time = time.time()
linear_search(large_array, target)
print(f"Ricerca lineare ha impiegato: {time.time() - start_time:.6f} secondi")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Ricerca binaria ha impiegato: {time.time() - start_time:.6f} secondi")