Il problema della ricerca di un elemento in un array è molto diffuso.
Data una sequenza di elementi sotto forma di array, si vuole determinare se uno specifico elemento (chiave) è presente o meno all’interno della sequenza.
Nel corso dell’articolo si farà riferimento ad array di tipo numerico ed, in particolare, di tipo intero e si prenderanno in esame tre tra gli algoritmi di ricerca più diffusi.
Due sono i casi a cui si può andare incontro:
- La sequenza di elementi non è ordinata;
- La sequenza di elementi è ordinata;
Argomenti trattati:
Ricerca lineare
Nel caso in cui la sequenza di elementi non è ordinata, è necessario utilizzare la cosiddetta ricerca lineare o sequenziale. Poiché non è possibile stabilie a priori in quale parte dell’array potrebbe trovarsi l’elemento da ricercare, è necessario analizzare gli elementi dell’array in sequenza e confrontartli con l’elemento (chiave) da ricercare per determinare se fa parte della sequenza. Se si vuole trovare solo la prima occorrenza della chiave, è possibile terminare la ricerca non appena la chiave viene trovata, senza dover scorrere interamente la sequenza.
Segue un’immagine animata che mostra il funzionamento della ricerca lineare con una chiave di valore 37:
Implementazione
public static int ricercaLineare(int[] arr, int chiave)
{
for (int i=0; i<arr.length; i++)
if (arr[i]==chiave)
return i;
return -1;
}
L’algoritmo è molto semplice: finché non si raggiunge la fine della sequenza, si verifica se l’elemento corrente è uguale alla chiave; in caso affermativo si restituisce l’indice di tale elemento interrompendo l’operazione di ricerca. Diversamente, si procede fino alla fine della sequenza e, se la chiave non è stata trovata, si restituisce il valore -1.
Con alcune piccole modifiche è possibile utilizzare la ricerca lineare per determinare il numero di occorrenze, ovvero il numero di volte che la chiave appare nella sequenza.
public static int ricercaLineareOccorrenze(int[] arr, int chiave)
{
int occorrenze = 0;
for (int i=0; i<arr.length; i++)
if (arr[i]==chiave)
occorrenze++;
return occorrenze;
}
Il funzionamento di quest’algoritmo è pressocché identico a quello precedente, ad eccezione del fatto che ci si avvale della variabile occorrenze per tenere traccia del numero di volte che la chiave è stata trovata all’interno della sequenza.
complessitÀ computazionale
TEMPO DI ESECUZIONE
Le operazioni di inizializzazione variabile, confronto, incremento e restituzione di un valore intero hanno un tempo di esecuzione pari ad O(1). Il tempo di esecuzione dell’algoritmo è dato dalla complessità del corpo del ciclo for per il numero di volte in cui esso viene eseguito.
- Caso peggiore: l’elemento ricercato è l’ultimo dell’array o non è presente;
- Caso medio: se ogni elemento è equamente distribuito, ciascun elemento ha la stessa probabilità di essere trovato (O(N/2) —> O(N));
- Caso migliore: l’elemento ricercato è il primo dell’array;
spazio di esecuzione
Lo spazio utilizzato dall’algoritmo è pari ad O(1) perché non vengono utilizzate strutture dati supplementari.
Ricerca binaria
Nel caso in cui la sequenza di elementi è ordinata, è possibile utilizzare la ricerca binaria, un algoritmo molto più efficiente della ricerca lineare. Il processo, che continua finché non si trova l’elemento da ricercare o finché non si raggiunge la fine della sequenza è il seguente:
- Si confronta la chiave con l’elemento centrale della sequenza;
- Se la chiave è uguale all’elemento centrale, la ricerca termina;
- Se la chiave è maggiore dell’elemento centrale, si prosegue la ricerca nella sottosequenza di destra;
- Se invece la chiave è minore dell’elemento centrale, si prosegue la ricerca nella sottosequenza di sinistra;
Segue un’immagine animata che mostra il funzionamento della ricerca binaria con una chiave di valore 37:
Implementazione
public static int ricercaBinaria(int arr[], int chiave)
{
int inf = 0, sup = arr.length - 1;
while (inf <= sup)
{
int med = (inf + sup)/ 2;
if (arr[med] == chiave)
return m;
if (arr[med] < chiave)
inf = med + 1;
else
sup = med - 1;
}
return -1;
}
Si utilizzano le variabili inf e sup per delimitare la porzione di array che andrà analizzata ad ogni iterazione. Di volta in volta, si utilizza la variabile m per indicare l’elemento centrale dell’array che andrà confrontato con il valore chiave. Tale confronto lascia spazio a tre possibilità:
- L’elemento centrale è uguale alla chiave: la ricerca termina e viene restituito il valore di med;
- L’elemento centrale è minore della chiave: la ricerca prosegue nella parte destra dell’array ed il primo elemento della nuova porzione da analizzare sarà quello in posizione med+1;
- L’elemento centrale è maggiore della chiave: la ricerca prosegue nella parte sinistra dell’array e l’ultimo elemento della nuova porzione da analizzare sarà quello in posizione med-1;
Le iterazioni continueranno finché inf non è minore o uguale a sup. Nel caso in cui inf diventasse maggiore di sup, la chiave non è presente nell’array: le iterazioni terminano e viene restituito il valore -1.
complessitÀ computazionale
TEMPO DI ESECUZIONE
Le operazioni di inizializzazione delle variabili, confronto e restituzione di un valore intero hanno un tempo di esecuzione pari ad O(1). Il tempo di esecuzione dell’algoritmo è dato dalla complessità del corpo del ciclo while per il numero di volte in cui esso viene eseguito.
- Caso peggiore: l’elemento ricercato non è presente nell’array. Poiché ad ogni iterazione la dimensione degli elementi analizzati viene dimezzata, verrano effettuati log2N confronti;
- Caso medio: verranno effettuati circa la metà dei confronti del caso peggiore, quindi
; - Caso migliore: l’elemento ricercato si trova nella posizione centrale dell’array;
spazio di esecuzione
Lo spazio utilizzato dall’algoritmo è pari ad O(1) perché non vengono utilizzate strutture dati supplementari.
Ricerca INTERPOLATA
Nel caso in cui la sequenza di elementi è ordinata e gli elementi sono equidistribuiti (la differenza fra due valori contigui è pressoché costante), è possibile utilizzare anche la ricerca interpolata, che può rivelarsi ancora più efficiente della ricerca binaria. Per comprendere meglio il principio sul quale si basa tale ricerca, è utile prendere come esempio il caso nel quale ricerchiamo un nominativo in un elenco telefonico. Se il nominativo ricercato inizia per B, non apriremo l’elenco in posizione centrale come si farebbe con la ricerca binaria, piuttosto lo apriremo in una posizione abbondantemente precedente a quella centrale. Si utilizza quindi l’informazione dell’elemento da cercare per tentare di determinare una posizione nella quale ci sembra più probabile trovare l’elemento.
Come l’algoritmo di ricerca binaria, la ricerca interpolata restringe ripetutamente la sequenza sulla quale effettuare la ricerca, ma il punto di divisione non è più quello centrale, bensì quello calcolato mediante l’interpolazione che permette di determinare la posizione nella quale è più probabile trovare l’elemento.
In particolare, per il calcolo di tale posizione, si utilizza la seguente formula:
Implementazione
public static int ricercaInterpolata(int arr[], int chiave){
int inf = 0, sup = (arr.length - 1);
while (inf <= sup && chiave >= arr[inf] && chiave <= arr[sup]){
int posizione = inf + (((sup-inf) / (arr[sup]-arr[inf]))*(chiave - arr[inf]));
if (arr[pos] == chiave)
return pos;
if (arr[pos] < chiave)
inf = pos + 1;
else
sup = pos - 1;
}
return -1;
}
Si utilizzano le variabili inf e sup per delimitare la porzione di array che andrà analizzata ad ogni iterazione. Di volta in volta, si utilizza la variabile posizione per indicare l’elemento dell’array che andrà confrontato con il valore chiave. Tale confronto lascia spazio a tre possibilità:
- L’elemento confrontato è uguale alla chiave: la ricerca termina e viene restituito il valore di posizione;
- L’elemento confrontato è minore della chiave: la ricerca prosegue nella parte destra dell’array ed il primo elemento del nuovo intervallo sarà quello in posizione posizione+1;
- L’elemento confrontato è maggiore della chiave: la ricerca prosegue nella parte sinistra dell’array e l’ultimo elemento del nuovo intervallo sarà quello in posizione posizione-1;
Le iterazioni continueranno finché inf non è minore o uguale a sup e finché il valore della chiave è compreso tra i valori minimo e massimo dell’intervallo preso in esame. Se l’elemento non viene trovato, viene restituito il valore -1.
complessitÀ computazionale
TEMPO DI ESECUZIONE
Le operazioni di inizializzazione delle variabili, confronto e restituzione di un valore intero hanno un tempo di esecuzione pari ad O(1). Il tempo di esecuzione è dato dalla complessità del corpo del ciclo while per il numero di volte in cui esso viene eseguito.
- Caso migliore: l’elemento ricercato si trova nella posizione calcolata mediante la formula di interpolazione alla prima iterazione;
- Caso peggiore: tutti gli elementi dell’array sono equidistribuiti, ad eccezione dell’ultimo che è molto più grande degli altri e l’elemento cercato è il penultimo, oppure quando tutti gli elementi sono equidistribuiti ad eccezione del primo che è molto più piccolo degli altri e l’elemento ricercato è in seconda posizione;
- Caso medio: gli elementi dell’array sono equidistribuiti;
spazio di esecuzione
Lo spazio utilizzato dall’algoritmo è pari ad O(1) perché non vengono utilizzate strutture dati supplementari.
