Problemi algoritmici di ricerca

9.1 Esempi di problemi risolti con ricerca lineare e binaria

Ricerca lineare

Problema: Ricerca di un elemento in un array: Dato un array di numeri e un valore target. Devi trovare l'indice del valore target nell'array.

Soluzione: Usiamo la ricerca lineare per controllare ogni elemento dell'array.

Esempio di implementazione:

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
print(linear_search(arr, target))  # Output: 2

Ricerca binaria

Problema: Ricerca di un elemento in un array ordinato: Dato un array ordinato di numeri e un valore target. Devi trovare l'indice del valore target nell'array.

Soluzione: Usiamo la ricerca binaria per dividere l'array a metà e cercare il valore target.

Esempio di implementazione:

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
print(binary_search(sorted_array, target))  # Output: 3

9.2 Problemi di utilizzo delle hash table per ottimizzare la ricerca

1. Ricerca di duplicati in un array

Problema: Dato un array di numeri. Devi trovare e restituire tutti i duplicati nell'array.

Soluzione: Usiamo una hash table per tenere traccia dei numeri già incontrati. Se un numero appare di nuovo, lo aggiungiamo alla lista dei duplicati.

Esempio di implementazione:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Esempio di utilizzo
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Output: [2, 4]

2. Trovare coppie con una somma data

Problema: Dato un array di numeri e un valore di somma target. Devi trovare tutte le coppie di numeri che sommate danno il valore target.

Soluzione: Usiamo una hash table per memorizzare i numeri e controllare se possono formare una coppia con il numero corrente che dia la somma target.

Esempio di implementazione:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Esempio di utilizzo
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Output: [(1, 5), (7, -1), (1, 5)]

9.3 Utilizzo combinato di diversi metodi di ricerca

In problemi complessi, spesso è necessario utilizzare vari metodi di ricerca per ottenere la massima efficienza. L'uso combinato di ricerca lineare, ricerca binaria e hash table consente di risolvere i problemi in modo più efficiente e flessibile.

Esempio 1: Ricerca di un elemento in un array e verifica della sua esistenza in un altro array

Dati due array di numeri. Devi trovare gli elementi del primo array che esistono nel secondo array.

Soluzione:

• Utilizziamo una hash table per memorizzare gli elementi del secondo array.
• Per ogni elemento del primo array verifichiamo la sua esistenza nella hash table.

Esempio di implementazione:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # Hash table per il secondo array
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# Esempio di utilizzo:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Output: [3, 4, 5]

Esempio 2: Verifica se un sottoarray è un array di anagrammi tramite hash table

Dato un array di stringhe e un modello di stringa. Devi verificare se una qualsiasi sottostringa dell'array di stringhe è un anagramma del modello.

Soluzione:

• Utilizziamo una hash table per contare la frequenza dei caratteri nel modello.
• Passiamo sull'array di stringhe e usiamo una "finestra scorrevole" per controllare ogni sottostringa rispetto alle frequenze dei caratteri.

Esempio di implementazione:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# Esempio di utilizzo:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Output: True

9.4 Esercizi pratici per consolidare il materiale

Esercizio 1: Ricerca di un elemento in un array non ordinato

Dato un array di numeri e un valore target. Devi trovare l'indice del valore target nell'array. Usa la ricerca lineare.

Esempio:

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

# Esempio di utilizzo:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Output: 2

Esercizio 2: Ricerca di duplicati in un array

Dato un array di numeri. Trova e restituisci tutti i duplicati nell'array utilizzando una hash table.

Esempio:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Esempio di utilizzo:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # Output: [3, 1]