6 tipi di algoritmi di ricerca e come funzionano

Puoi immaginare gli algoritmi di ricerca come investigatori digitali che trovano ciò di cui hai bisogno in vaste collezioni di dati, come siti web o database, con il minor numero di passaggi possibile.

Da Google e Amazon a Facebook e Netflix, gli algoritmi di ricerca svolgono un ruolo vitale nelle interazioni digitali nella vita quotidiana.

In questo articolo, imparerai i tipi più comuni di algoritmi di ricerca, le loro complessità temporali, come funzionano i loro processi di ricerca e le applicazioni pratiche nell’informatica.

Una complessità media inferiore è migliore per ottenere prestazioni più veloci, soprattutto con input di grandi dimensioni. Algoritmi come la ricerca binaria O(log n) sono altamente efficienti.

D’altra parte, complessità più elevate, come O(n), possono diventare impraticabili per grandi insiemi di dati a causa di una crescita lineare o di tempi di esecuzione peggiori. Tuttavia, l’efficienza dipende anche da fattori come la struttura dei dati, il contesto del problema, le risorse e i requisiti dell’applicazione.

1. Algoritmi di ricerca lineare

La ricerca lineare, o ricerca sequenziale, itera in sequenza ogni elemento dell’array in un set di dati, confrontandolo con l’elemento target fino a quando non trova una corrispondenza.  Se la funzione di ricerca raggiunge la fine dell’array senza trovare una corrispondenza, segnala che l’elemento target non è presente nel set di dati.

L’elemento target  che stai cercando può essere un numero, una stringa, un oggetto o qualsiasi altro tipo di dato che può essere memorizzato in un array. Questa flessibilità rende la ricerca lineare un algoritmo versatile che può essere applicato a un’ampia gamma di tipi di dati.

Per illustrare meglio questo processo di ricerca, vediamo un esempio reale.

Supponiamo di avere un elenco non ordinato di numeri interi che rappresentano l’età delle persone di un gruppo. Ti viene chiesto di scoprire se una determinata età, ad esempio 25 anni, è presente nell’array. Partiresti dall’inizio dell’array e controlleresti ogni elemento, uno per uno, fino a trovare l’età di 25 anni o a raggiungere la fine dell’array.

Il tempo di esecuzione di un algoritmo di ricerca lineare è proporzionale alla dimensione dell’array. La complessità computazionale della ricerca lineare è O(n), dove n è il numero di elementi dell’array.

Applicazioni della ricerca lineare

• Attività di ricerca semplici: La ricerca lineare viene spesso utilizzata per un’ampia gamma di task di ricerca di base, quando il set di dati è piccolo o quando la complessità aggiuntiva di altri algoritmi non è giustificata. Ad esempio, la ricerca all’interno di un piccolo elenco di nomi o numeri.
• Strutture dati lineari: La ricerca lineare è fondamentale per molte strutture di dati lineari come array, liste e pile. In genere viene utilizzata per la scansione di queste strutture al fine di individuare elementi specifici o per eseguire operazioni.
• Array non ordinati: Poiché la ricerca lineare controlla ogni elemento in modo sequenziale, può individuare gli elementi indipendentemente dalla loro posizione nell’array.

2. Algoritmo di ricerca binaria

La ricerca binaria è un algoritmo efficiente utilizzato per trovare un valore target all’interno di un elenco ordinato. L’algoritmo divide ripetutamente l’intervallo di ricerca a metà utilizzando il metodo della ricerca binaria. Poi controlla il valore target rispetto all’elemento centrale e procede verso la parte destra o sinistra dell’array. Questo processo continua fino a quando non viene trovato il valore target. L’intervallo di ricerca risulta massimo quando l’obiettivo non è presente nell’array.

Vediamo un esempio di utilizzo della ricerca binaria per trovare un valore numerico specifico.

Immaginiamo di avere un array di numeri  [2,5,8,12,16,23,38,56,72,91] e che tu voglia trovare il numero 23.

Comincia a guardare l’elemento centrale (nodo radice), che è 16. Dal momento che 23 è più grande di 16, guarda solo i numeri a destra di 16. Successivamente, guarda l’elemento centrale di questa parte, che è 56. Dato che 23 è più piccolo di 56, guarda solo i numeri alla sinistra di 56. Ora guarda nuovamente l’elemento centrale, che è 23. Hai trovato la chiave di ricerca!

Il tempo di esecuzione di un algoritmo di ricerca binaria è O (log n), dove n è il numero di elementi dell’array.

Applicazioni della ricerca binaria

• Ricerca nei database: È un algoritmo efficace per la ricerca nei database per individuare rapidamente i record basati su campi indicizzati, come gli ID o le chiavi.
• Ricerca di elementi in array ordinati: La ricerca binaria individua in modo efficiente gli elementi in array ordinati, il che è utile nelle strutture di dati indicizzate e in applicazioni come la ricerca di una parola in un dizionario o la ricerca di un elemento in un elenco ordinato.
• Fondamenti algoritmici: Serve come componente fondamentale per sviluppare sofisticati algoritmi di apprendimento automatico. La ricerca binaria aiuta ad addestrare le reti neurali e a ottimizzare gli iperparametri del modello.
• Ottimizzazione degli algoritmi: La ricerca binaria viene utilizzata negli algoritmi, comprese le strategie divide et impera, per risolvere in modo efficiente problemi come la ricerca di radici quadrate o la localizzazione di elementi di picco negli array.
• Ricerca negli alberi: Gli alberi di ricerca binaria (BST) utilizzano questo algoritmo per cercare, inserire ed eliminare elementi in modo efficiente mantenendo l’ordine dell’albero.

3. Ricerca per interpolazione

Quando i valori in un array ordinato sono distribuiti in modo uniforme, la ricerca per interpolazione offre un vantaggio rispetto alla ricerca binaria. L’interpolazione prevede la creazione di nuovi punti dati all’interno dell’intervallo dello spazio di ricerca conosciuto.

Mentre la ricerca binaria si concentra sempre sull’elemento centrale, la ricerca per interpolazione regola la sua posizione di ricerca in base al valore target che viene ricercato. Ad esempio, se la chiave di ricerca è più vicina alla fine, la ricerca per interpolazione tende a iniziare la ricerca dai dati di quell’estremità.

Per mettere le cose in prospettiva, immaginiamo che tu stia cercando un prezzo particolare all’interno di un elenco di prezzi di articoli in un negozio. Questi prezzi sono disposti dal più basso al più alto. Invece di controllare sempre la metà dell’elenco (come nella ricerca binaria), la ricerca per interpolazione stima dove potrebbe cadere il prezzo in base al suo valore rispetto ai prezzi più bassi e più alti. Poi, si ripete questo processo finché non si trova il prezzo.

Il tempo di esecuzione di un algoritmo di ricerca per interpolazione è O(log log n), dove n è il numero di elementi dell’array.

Applicazioni della ricerca per interpolazione

• Ricerca nei database: La ricerca per interpolazione è comunemente utilizzata nei database per cercare record basati su alcuni elementi chiave.
• Ricerca in array di grandi dimensioni: Questo algoritmo di ricerca facilita una ricerca più efficiente in grandi array ordinati, soprattutto quando la distribuzione dei valori è uniforme. Può essere applicato in vari campi come l’informatica scientifica, dove è necessario cercare in modo efficiente in grandi serie di dati.
• Recupero di dati da tabelle di simboli: La ricerca per interpolazione può essere utilizzata nelle tabelle di simboli, dove le chiavi sono associate ai valori. Ad esempio, nei linguaggi di programmazione, le tabelle di simboli vengono utilizzate per memorizzare variabili, funzioni e altri identificatori. La ricerca per interpolazione può individuare rapidamente le informazioni associate a un identificatore specifico.
• Applicazioni sensibili al tempo: Grazie alla sua capacità di recuperare rapidamente i dati, la ricerca per interpolazione è adatta alle applicazioni sensibili al tempo.
• Tabelle hash: Efficienti per trovare i dati se combinate con una funzione hash.

4. Ricerca a salti

La ricerca a salti, nota anche come ricerca di blocchi, è progettata in modo specifico per gli array ordinati. A differenza della ricerca lineare, che esamina ogni elemento in modo sequenziale, la ricerca a salti procede a balzi per incrementi dal valore prefissato, bypassando numerosi elementi per una ricerca più veloce.

Se l’elemento target si trova all’interno di un intervallo specificato, l’algoritmo impiega una ricerca lineare all’interno di quel blocco. Questo approccio riduce notevolmente le operazioni, migliorando l’efficienza della ricerca.

Vediamo un esempio dell’algoritmo di ricerca a salto.

Immagina di dover trovare un numero specifico in un lungo elenco di numeri e di volerlo fare in modo più veloce rispetto a controllare ogni numero uno per uno.

1. Decidi quanti numeri saltare ogni volta che cerchi: Diciamo che salterai 3 numeri alla volta.
2. Inizia a scorrere l’elenco, saltando ogni volta il numero scelto, finché non trovi un numero uguale o superiore a quello che stai cercando.
3. Una volta individuato un intervallo in cui potrebbe trovarsi il numero, esegui una ricerca lineare fino a trovare quello desiderato.

Il tempo di esecuzione di un algoritmo di ricerca a salto è O(√n), dove n è il numero di elementi dell’array ordinato.

Applicazioni della ricerca a salti

• Applicazioni JavaScript: La ricerca a salti ottimizza il processo di ricerca nelle applicazioni JavaScript, migliorando l’efficienza e la responsività.
• Ricerca nei sistemi di database: Questo algoritmo cerca i record in base ad alcuni elementi chiave in database di grandi dimensioni.
• Recupero di dati da supporti visivi: La ricerca a salti individua in modo efficiente un fotogramma specifico all’interno di un file video di grandi dimensioni facendo avanzare un numero fisso di fotogrammi alla volta.

5. Ricerca esponenziale

L’algoritmo di ricerca esponenziale,  nota anche come ricerca al quadrato, si differenzia dalla ricerca a salti per il modo in cui divide l’array e per il tipo di ricerca impiegato all’interno di queste divisioni. Mentre la ricerca a salto divide l’array in blocchi e utilizza la ricerca lineare, la ricerca esponenziale divide l’array utilizzando potenze esponenziali di 2 e applica la ricerca binaria.

In sostanza, la funzione di ricerca attraversa in modo esponenziale l’intero array, partendo da sinistra, segmentandolo in blocchi più piccoli utilizzando potenze di 2. L’algoritmo conduce una ricerca binaria all’interno di ciascuno di questi blocchi fino a trovare l’obiettivo.

Poiché questo algoritmo di ricerca può essere un po’ complesso, vediamo di illustrarne il funzionamento applicandolo a uno scenario reale.

Immagina di avere una libreria piena di libri ordinati alfabeticamente per titolo. Stai cercando un libro specifico, diciamo “Harry Potter e la Pietra Filosofale”. Invece di cercare ogni libro uno per uno, decidi di utilizzare la ricerca esponenziale.

Ecco come funziona:

1. Punto di partenza: Inizi con il primo libro sul lato sinistro della libreria. Se non è il libro che stai cercando, procedi.
2. Spostati a destra, raddoppiando la finestra di ricerca: Se trovi “Harry Potter e la Pietra Filosofale” in una di queste posizioni, hai trovato il tuo libro.
3. Ripeti il processo: Continua a ripetere il processo, raddoppiando ogni volta il raggio d’azione, finché non trovi il libro.

Anche se non è l’applicazione esatta della ricerca esponenziale, questo esempio dimostra come sia possibile individuare rapidamente il libro senza dover passare in rassegna tutti i libri uno per uno.

Il tempo di esecuzione di un algoritmo di ricerca esponenziale è O(log n), dove n è il numero di elementi dell’array ordinato.

Applicazioni della ricerca esponenziale

• Trovare dati in grandi array ordinati: La ricerca esponenziale trova rapidamente gli elementi in grandi array ordinati, ad esempio nei product listing estendendo esponenzialmente il raggio di ricerca, il che è l’ideale per le situazioni in cui la ricerca lineare è troppo lenta.
• Ricerca nei file system: Questo algoritmo migliora la ricerca nei file system trovando rapidamente file o directory all’interno di strutture di directory grazie all’espansione esponenziale dell’intervallo di ricerca.

6. Ricerca ternaria

La ricerca ternaria è un algoritmo di ricerca utilizzato per trovare la posizione di un valore specifico in un array o in un elenco ordinato. A differenza delle ricerca binaria, divide l’intervallo di ricerca in tre parti invece che in due. Confrontando il valore target con gli elementi in due punti e dividendo l’array in tre parti, la funzione di ricerca restringe in modo efficiente lo spazio di ricerca.

Per illustrare un esempio, applichiamo la ricerca ternaria per trovare il numero 6 nell’array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

• Dividi l’area di ricerca:
  • Dividi la tua area di ricerca in tre parti  individuando due punti di separazione: Un punto si trova a circa un terzo della distanza da sinistra (diciamo 4) e l’altro a circa due terzi da sinistra (diciamo 8).
  • In questo modo l’area è divisa in [1, 4], (5, 8) e [9, 10].
• Confronta con l’obiettivo
  • Controlla se il numero che stai cercando (6) è uguale a 4 o a 8.
  • Non è uguale né a 4 né a 8, quindi aggiusta i puntatori in base a dove potrebbe trovarsi il 6:
    • Dato che 6 è maggiore di  4 ma inferiore a 8, spostiamo il puntatore sinistro su 5 e quello destro su 7.
  • Continua a ripetere questo processo con lo spazio di ricerca ridotto fino a quando trovi il 6 o non hai più spazio dove cercare.
  • Alla fine restringi l’area di ricerca  a [6,6] e trovi il numero che stai cercando!

Il tempo di esecuzione di un algoritmo di ricerca ternaria è O(log3 n), dove n è il numero di elementi dell’array ordinato.

Applicazioni della ricerca ternaria

• Funzioni unimodali: La ricerca ternaria viene applicata alle funzioni unimodali per identificare i loro valori massimi o minimi. Le funzioni unimodali sono quelle che hanno un unico valore massimo.

Conclusione

Le applicazioni di diversi tipi di algoritmi di ricerca sono vaste e diversificate, spaziando dalla ricerca in grandi database, all’ottimizzazione delle applicazioni, fino a fungere da blocchi fondamentali per lo sviluppo di algoritmi avanzati di apprendimento automatico per la ricerca.

Tenendo presente le complessità temporali e spaziali, le capacità, combinate con i vantaggi e gli svantaggi di ciascuno degli algoritmi menzionati, è possibile prendere decisioni consapevoli. Che si tratti di un compito per la lezione di informatica o dello sviluppo della prossima app rivoluzionaria, padroneggiando tecniche come la ricerca binaria, DFS, BFS e il divide-and-conquer, è possibile sbloccare il pieno potenziale delle strutture dati e migliorare le prestazioni del sistema.

Se stai creando o valutando la ricerca per un negozio online in particolare, i meccanismi funzionano un po’ diversamente nella pratica. Vedi come funziona la ricerca nel commercio elettronico dietro le quinte.

Domande frequenti