Ricerca lineare

1.1 Definizione di ricerca lineare

La ricerca lineare (conosciuta anche come ricerca sequenziale) è un algoritmo per trovare un elemento in una lista o array che verifica sequenzialmente ogni elemento finché non trova una corrispondenza o non ha controllato tutti gli elementi. È l'algoritmo di ricerca più semplice che non richiede un ordinamento preliminare dei dati.

Principi fondamentali:

• Verifica sequenziale: L'algoritmo esplora ogni elemento dell'array o lista, confrontandolo con il valore cercato.
• Interruzione della ricerca: La ricerca si interrompe quando viene trovato un elemento che corrisponde al valore cercato o quando tutti gli elementi sono stati controllati.
• Non richiede ordinamento: La ricerca lineare può essere applicata a dati non ordinati.
• Applicazione: La ricerca lineare può essere applicata a qualsiasi struttura di dati che supporta iterazione, inclusi liste e array.

La ricerca lineare ha una complessità temporale di O(n), dove n è il numero di elementi nell'array o lista. Nel peggiore dei casi, l'algoritmo dovrà verificare tutti gli n elementi per trovare il valore cercato o determinare la sua assenza.

Analisi della complessità temporale:

• Miglior caso (Best case): L'elemento viene trovato al primo posto, O(1).
• Medio caso (Average case): L'elemento viene trovato da qualche parte nel mezzo, O(n/2), che è equivalente a O(n).
• Peggior caso (Worst case): L'elemento viene trovato all'ultimo posto o è assente, O(n).

1.2 Implementazione passo passo della ricerca lineare

Passi della ricerca lineare:

• Inizializzazione: Impostare l'indice iniziale per la ricerca (di solito l'indice zero).
• Verifica sequenziale: Verificare ogni elemento della lista o array per corrispondenza con il valore cercato.
• Condizione di termine: Se l'elemento è trovato, restituire il suo indice. Se tutti gli elementi sono stati verificati e il valore cercato non è stato trovato, restituire un valore speciale (di solito -1 o None).

Implementazione della ricerca lineare in Python:

def linear_search(arr, target):
    # Verifichiamo ogni elemento dell'array
    for index, element in enumerate(arr):
        # Se l'elemento corrente è uguale al valore cercato, restituiamo il suo indice
        if element == target:
            return index
    # Se l'elemento non è trovato, restituiamo -1
    return -1

Spiegazione passo passo dell'implementazione:

• Inizializzazione del ciclo: Si usa il ciclo for con la funzione enumerate, che restituisce l'indice e l'elemento dell'array a ogni iterazione.
• Confronto: A ogni iterazione l'elemento corrente viene confrontato con il valore cercato (target).
• Restituzione dell'indice: Se l'elemento corrente è uguale al valore cercato, viene restituito l'indice di questo elemento.
• Restituzione di -1: Se il ciclo si completa e l'elemento cercato non è stato trovato, restituiamo -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}")  # Output: 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}")  # Output: Elemento 5 trovato all'indice -1

1.3 Esempi di problemi risolti con la ricerca lineare

La ricerca lineare è usata per risolvere molti problemi legati alla ricerca di elementi nelle collezioni di dati. Ecco alcuni esempi di tali problemi:

Problema 1: Ricerca di un elemento in un array

Bisogna trovare un numero dato in un array di numeri.

Esempio:

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

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Elemento {target} trovato all'indice {index}")  # Output: Elemento 70 trovato all'indice 3

Problema 2: Verifica della presenza di un elemento in una lista

Bisogna verificare se un valore dato è presente in una lista di stringhe.

Esempio:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Elemento {target} {'trovato' if found else 'non trovato'}")  # Output: Elemento cherry trovato

Problema 3: Ricerca del minimo o massimo elemento

Bisogna trovare il valore minimo o massimo in una lista.

Esempio:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Valore minimo: {min_value}")  # Output: Valore minimo: 2

Problema 4: Ricerca della prima occorrenza

Trovare la prima occorrenza di un elemento dato in una lista.

Esempio:

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

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Prima occorrenza di {target} all'indice {index}")  # Output: Prima occorrenza di 2 all'indice 1

Problema 5: Conteggio delle occorrenze

Contare il numero di occorrenze di un elemento dato in una lista.

Esempio:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Elemento {target} appare {count} volte")  # Output: Elemento 2 appare 3 volte