Il problema della ricerca è trovare, all’interno di un vettore, l’indice in cui compare un valore chiamato chiave. Gli algoritmi più importanti per iniziare sono la ricerca lineare e la ricerca binaria. Prima di programmarli, chiediti sempre se il vettore è ordinato.

Ricerca lineare: controllare un elemento alla volta

La ricerca lineare confronta la chiave con ogni elemento, da sinistra verso destra. Funziona anche quando il vettore non è ordinato. Nell’esempio, -1 segnala che il valore non è stato trovato.

static int RicercaLineare(int[] v, int chiave)
{
    for (int i = 0; i < v.Length; i++)
    {
        if (v[i] == chiave) return i;
    }
    return -1;
}

int[] dati = { 8, 3, 6, 1, 4 };
Console.WriteLine(RicercaLineare(dati, 6)); // 2

Ricerca binaria: dimezzare l’intervallo

La ricerca binaria richiede il vettore ordinato. Confronta la chiave con l’elemento centrale; se è più piccola continua nella metà sinistra, se è più grande nella metà destra. A ogni passo scarta circa metà degli elementi ancora candidati.

static int RicercaBinaria(int[] v, int chiave)
{
    int sinistra = 0;
    int destra = v.Length - 1;
    while (sinistra <= destra)
    {
        int medio = sinistra + (destra - sinistra) / 2;
        if (v[medio] == chiave) return medio;
        if (v[medio] < chiave) sinistra = medio + 1;
        else destra = medio - 1;
    }
    return -1;
}

int[] ordinato = { 1, 3, 4, 6, 8, 10 };
Console.WriteLine(RicercaBinaria(ordinato, 6)); // 3

Confronto e complessità

Su un vettore di 1.024 elementi, una ricerca binaria richiede al massimo circa 11 confronti con la versione mostrata (può controllare anche il punto finale), mentre una ricerca lineare potrebbe dover esaminare tutti i 1.024 elementi. Tuttavia, se bisogna prima ordinare i dati, va considerato anche il costo dell’ordinamento.

Tabella di traccia della ricerca binaria

Errori frequenti

• Usare la ricerca binaria su un vettore non ordinato.
• Scrivere sinistra < destra invece di sinistra <= destra e saltare l’ultimo candidato.
• Non aggiornare gli estremi con medio + 1 e medio - 1, provocando cicli senza avanzamento.
• Interpretare l’indice come posizione a partire da 1: in C# gli indici partono da 0.

Esercizi

• Traccia la ricerca binaria di 7 in [1, 3, 4, 7, 9, 12, 15].
• Cerca 5 nello stesso vettore e verifica perché il risultato è -1.
• Scrivi una funzione che conti il numero di confronti della ricerca lineare, poi confrontalo con quello della ricerca binaria.

Nel percorso: ← Ordinamento · Indice del corso