Una delle operazioni più frequentemente eseguita su una collezione di dati è la ricerca di un particolare valore, al fine di determinarne la presenza o meno nella collezione.

Se non si ha nessuna informazione in merito alla disposizione dei dati, l'unica strategia di ricerca possibile è la scansione lineare o ricerca sequenziale.
Tale algoritmo prevede la scansione in sequenza di tutti gli elementi della collezione, per verificare la presenza del valore da cercare.
La ricerca si arresta quando il valore viene trovato oppure quando si esaurisce la sequenza.
In caso la collezione di elementi fosse notevolmente numerosa, una tale strategia di ricerca sarebbe poco efficiente e molto onerosa in termini di tempo.

Se invece la collezione di elementi fosse ordinata (in modo crescente o decrescente), si potrebbe attuare una strategia molto più efficiente, nota come ricerca binaria o dicotomica.

Se, in aggiunta all'ordinamento, si avessero anche delle informazioni sulla distribuzione dei valori all'interno della sequenza, la strategia risolutiva potrebbe essere ancora più ottimizzata ed eseguire una ricerca simile a quella binaria, nota come ricerca interpolata.

Vediamo un po' più nello specifico le principali strategie citate.

Come indicato poc'anzi, se non si hanno informazioni in merito alla disposizione dei dati, l'unica strategia di ricerca attuabile è la scansione lineare, ossia l'attraversamento della collezione, dal primo elemento all'ultimo, fino a che si trova l'elemento cercato o si esaurisce la sequenza.

L'algoritmo può essere implementato in due varianti, la prima, che restituisce semplicemente un valore boolean per indicare la presenza o meno del valore cercato nella collezione, la seconda, che restituisce la posizione del valore cercato nella sequenza, oppure il valore -1, nel caso in cui esso non fosse presente.

L'implementazione in Java di entrambe le varianti, per la ricerca di un valore stringa in una collezione di stringhe, potrebbe essere la seguente.

// prima variante
// cerca un valore nella collezione e restituisce 
// true se esso è presente, false in caso contrario
public static boolean cerca(String val, String[] collezione) {
    if (val == null) {
        return false;
    }
        
    for (int i = 0; i < collezione.length; i++) {
        if (val.equals(collezione[i])) {
            return true;
        }
    }
    return false;
}         

// seconda variante
// cerca un valore nella collezione e restituisce 
// la sua posizione oppure -1 se esso non è presente
public static int cerca(String val, String[] collezione) {
    if (val == null) {
        return -1;
    }
        
    for (int i = 0; i < collezione.length; i++) {
        if (val.equals(collezione[i])) {
            return i;
        }
    }
    return -1;
}

Tale tipo di ricerca richiede, nel caso peggiore, ossia qualora l'elemento da cercare fosse l'ultimo della collezione, oppure non fosse presente, un numero massimo di tentativi (confronti) pari al numero di elementi della collezione.
Nel caso migliore, ossia se l'elemento da cercare fosse il primo della sequenza, allora il numero di confronti sarebbe pari ad uno.
In media, si può concludere che occorrono n/2 confronti, dove n rappresenta il numero degli elementi della collezione.
Si dice che un tale algoritmo ha una complessità computazionale lineare e si indica con O(n), ad indicare che il tempo necessario per cercare un elemento cresce in modo lineare con il numero degli elementi della collezione.

Nei casi in cui occorre cercare un elemento all'interno di una sequenza ordinata, si possono mettere in atto strategie più efficienti rispetto alla banale ricerca sequenziale.
La ricerca binaria o dicotomica è possibile su una struttura che consente l'accesso diretto ai suoi elementi (es. un vettore).

Essa verifica la presenza dell'elemento da cercare secondo la logica che segue:

• l'elemento da cercare viene confrontato con l'elemento centrale della sequenza, se i due elementi sono uguali, la ricerca termina con successo
• se l'elemento centrale della sequenza è successivo (maggiore) all'elemento cercato, la ricerca viene ripetuta con la stessa logica sulla sottosequenza degli elementi a sinistra (minori) di quello centrale
• se l'elemento centrale della sequenza è precedente (minore) all'elemento cercato, la ricerca viene ripetuta con la stessa logica sulla sottosequenza degli elementi a destra (maggiori) di quello centrale
• la ricerca termina con esito negativo quando si giunge ad una sequenza di un solo elemento e questi non coincide con il valore da cercare

Il termine binaria o dicotomica sta infatti ad indicare che, ad ogni passo, la ricerca viene ristretta ad un numero di elementi dimezzato rispetto al passo precedente.

Tale algoritmo richiede, nel caso peggiore, un numero di tentativi pari al logaritmo in base 2 della dimensione della sequenza in cui cercare.
Nel caso migliore, invece, se l'elemento da cercare fosse quello centrale della sequenza, il numero di tentativi richiesti sarebbe pari ad uno.
In media, quindi, occorrerebbero log₂n tentativi per verificare la presenza di un valore in una sequenza di lunghezza pari ad n.
Si può, quindi, concludere affermando che la complessità di questo algoritmo è pari ad O(log₂n), ossia il tempo necessario per cercare un elemento cresce in modo logaritmico rispetto alla lunghezza della sequenza in cui cercare.
Esso risulterebbe, quindi, decisamente più efficiente del precedente algoritmo di ricerca sequenziale.

Vediamo come esso procederebbe attraverso un esempio grafico.
Supponiamo di dover cercare il valore 5 nel vettore seguente.

Il valore 5 verrebbe confrontato con l'elemento centrale della sequenza.

Tale valore risulta successivo al valore cercato, pertanto la ricerca può continuare, con la stessa logica, solo nella parte sinistra (elementi minori) della sequenza.

Si procede quindi confrontando l'elemento da cercare con l'elemento centrale di questa sottosequenza.

Tale valore risulta minore del valore cercato, per cui la ricerca può continuare, con la stessa logica, solo nella parte destra (elementi maggiori) della sequenza.

A questo punto il valore cercato coincide con quello centrale della sequenza, pertanto la ricerca termina con successo.

L'algoritmo che utilizza questa strategia risolutiva viene sviluppato principalmente in forma ricorsiva.
Anche questo algoritmo di ricerca può essere implementato in due varianti, la prima, che restituisce semplicemente un valore boolean per indicare la presenza o meno del valore cercato nella collezione, la seconda, che restituisce la posizione del valore cercato nella collezione, oppure il valore -1 nel caso in cui esso non fosse presente.

L'implementazione in Java di entrambe le varianti, per la ricerca di un valore stringa in una collezione di stringhe potrebbe essere la seguente.

// prima variante
// cerca un valore nella collezione e restituisce 
// true se esso è presente, false in caso contrario
// funzione principale che richiama la funzione ricorsiva che segue
public static boolean ricercaBinaria(String val, String[] collezione) {
    if (val == null) {
        return false;
    }

    return ricercaBinariaR(val, collezione, 0, collezione.length - 1);
}

// funzione ricorsiva richiamata anche dalla funzione precedente
public static boolean ricercaBinariaR(String val, String[] collezione, int iIniz, int iFin) {
    if (iIniz > iFin) {
        return false;
    }

    int iMed = (iIniz + iFin) / 2;
    if (val.equals(collezione[iMed])) {
        return true;
    } else if (val.compare(collezione[iMed]) < 0) {
        return ricercaBinariaR(val, collezione, iIniz, iMed - 1);
    } else {
        return ricercaBinariaR(val, collezione, iMed + 1, iFin);
    }
}

// seconda variante
// cerca un valore nella collezione e restituisce 
// la sua posizione oppure -1 se esso non è presente
// funzione principale che richiama la funzione ricorsiva che segue
public static int ricercaBinaria(String val, String[] collezione) {
    if (val == null) {
        return -1;
    }

    return ricercaBinariaR(val, collezione, 0, collezione.length - 1);
}

// funzione ricorsiva richiamata anche dalla funzione precedente
public static int ricercaBinariaR(String val, String[] collezione, int iIniz, int iFin) {
    if (iIniz > iFin) {
        return -1;
    }

    int iMed = (iIniz + iFin) / 2;
    if (val.equals(collezione[iMed])) {
        return iMed;
    } else if (val.compare(collezione[iMed]) < 0) {
        return ricercaBinariaR(val, collezione, iIniz, iMed - 1);
    } else {
        return ricercaBinariaR(val, collezione, iMed + 1, iFin);
    }
}

L'algoritmo di ricerca interpolata è un perfezionamento dell'algoritmo di ricerca binaria, utilizzabile nelle situazioni in cui, oltre alla presenza di una collezione ordinata, si abbiano anche informazioni sulla distribuzione degli elementi all'interno della collezione.

Per chiarire meglio il procedimento possiamo pensiamo al modo in cui solitamente procediamo per cercare un termine in un dizionario.

Osservando la prima lettera del termine da cercare, apriamo il dizionario in un punto che non corrisponde sempre alla sua pagina mediana, ma è spostato verso l'inizio o verso la fine del dizionario a seconda che tale prima lettera sia più prossima all'inizio o alla fine dell'alfabeto.

Ad esempio, se il termine da cercare iniziasse con la lettera B, apriremmo il dizionario in un punto prossimo all'inizio, viceversa, se il termine da cercase iniziasse con la lettera T, apriremmo il dizionario in un punto più prossimo alla fine dello stesso.

In termini pratici, la posizione dell'elemento da confrontare con il valore da cercare non corrisponde sempre alla posizione mediana della sequenza, ma bensì è determinato attraverso una funzione di interpolazione, che si basa sulle informazioni note in merito alla distribuzione degli elementi all'interno della collezione.

Non approfondiremo tale algoritmo di ricerca con la sua implementazione in Java.
Per gli scopi di questo sito è sufficiente conoscere che le sue prestazioni possono essere in alcuni casi migliori di quelle della ricerca binaria, infatti, la complessità computazionale di questo algoritmo può essere sintetizzata con O(log₂log₂n), dove n rappresenta sempre la lunghezza della collezione in cui cercare.