Algoritmi di Ricerca in C++ — Formazione Digitale

01 — Introduzione

Cosa significa cercare?

Cercare un elemento in un array significa determinare se un valore è presente e, in caso affermativo, restituire la sua posizione (indice). È una delle operazioni più frequenti in qualsiasi programma: ogni volta che cerchi un contatto, un prodotto o un record in un database, un algoritmo di ricerca sta lavorando.

Studieremo due approcci fondamentali: la ricerca lineare, che funziona su qualsiasi array, e la ricerca binaria, molto più veloce ma che richiede un array già ordinato.

📌 Prerequisiti Array monodimensionali in C++, cicli for e while, istruzione return. Per la ricerca binaria: concetto di array ordinato.

💡 Convenzione di ritorno Entrambi gli algoritmi restituiscono l'indice dell'elemento trovato, oppure -1 se l'elemento non è presente. Questa convenzione è standard in C++.

02 — Algoritmo

Ricerca Lineare

La ricerca lineare scansiona l'array dall'inizio alla fine, confrontando ogni elemento con il valore cercato. È l'algoritmo più semplice possibile: non richiede che l'array sia ordinato e funziona sempre.

Idea visiva

Con array [15, 42, 8, 73, 27, 61, 4] e target 27: si esamina 15 (no), 42 (no), 8 (no), 73 (no), 27 — trovato all'indice 4. Nel caso peggiore si scansiona tutto l'array senza trovare nulla.

⚠ Caso peggiore Se l'elemento non è presente, la ricerca lineare confronta tutti gli n elementi prima di restituire -1. Con array grandi (milioni di record) questo diventa inaccettabile.

Codice C++ commentato

C++ · ricerca_lineare.cpp

#include <iostream>
using namespace std;

// Cerca target nell'array, restituisce l'indice o -1 se non trovato
int ricercaLineare(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;  // trovato: restituisce l'indice
    }
    return -1;  // non trovato
}

int main() {
    int arr[] = {15, 42, 8, 73, 27, 61, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 27;

    int risultato = ricercaLineare(arr, n, target);

    if (risultato != -1)
        cout << "Trovato " << target << " all'indice " << risultato << endl;
    else
        cout << target << " non trovato nell'array" << endl;

    return 0;
}

Visualizzatore

Pronto. Imposta il valore e premi Play o Step.

Confronti: 0 Indice corrente: —

Non esaminato

Esaminato (no match)

Trovato

Escluso

03 — Algoritmo

Ricerca Binaria

La ricerca binaria sfrutta il fatto che l'array è già ordinato per eliminare metà degli elementi a ogni confronto. Confronta il valore cercato con l'elemento centrale: se è minore cerca nella metà sinistra, se è maggiore nella metà destra.

Idea visiva

Con array ordinato [4, 8, 15, 27, 42, 61, 73] e target 27: centro = 27 — trovato subito. Se cercassimo 61: centro=27 (minore, vai a destra), centro=61 — trovato in 2 confronti invece di 5 con la lineare.

📌 Prerequisito fondamentale La ricerca binaria funziona solo su array ordinati. Se applichi la ricerca binaria a un array non ordinato otterrai risultati sbagliati senza errori a runtime — uno dei bug più insidiosi per i principianti.

💡 Perché è così veloce? A ogni passo dimezza lo spazio di ricerca. Con 1000 elementi bastano al massimo 10 confronti (log₂ 1000 ≈ 10). Con un milione di elementi: al massimo 20 confronti. La ricerca lineare ne richiederebbe fino a 1.000.000.

Codice C++ commentato

C++ · ricerca_binaria.cpp

#include <iostream>
using namespace std;

// Cerca target in array ORDINATO, restituisce indice o -1
int ricercaBinaria(int arr[], int n, int target) {
    int low  = 0;      // indice sinistro (inizio intervallo)
    int high = n - 1;  // indice destro  (fine intervallo)

    while (low <= high) {
        int mid = low + (high - low) / 2;  // indice centrale (evita overflow)

        if (arr[mid] == target)
            return mid;           // trovato
        else if (arr[mid] < target)
            low = mid + 1;         // target è a destra: sposta low
        else
            high = mid - 1;        // target è a sinistra: sposta high
    }
    return -1;  // non trovato
}

int main() {
    // ATTENZIONE: l'array DEVE essere ordinato
    int arr[] = {4, 8, 15, 27, 42, 61, 73};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 61;

    int risultato = ricercaBinaria(arr, n, target);

    if (risultato != -1)
        cout << "Trovato " << target << " all'indice " << risultato << endl;
    else
        cout << target << " non trovato" << endl;

    return 0;
}

Visualizzatore

Pronto. Imposta il valore e premi Play o Step.

Confronti: 0 Intervallo: —

Non esaminato

Intervallo attivo

Elemento centrale (mid)

Trovato

Escluso

04 — Analisi

Confronto tra algoritmi

Algoritmo	Caso migliore	Caso medio	Caso peggiore	Array ordinato?
Ricerca Lineare	O(1)	O(n)	O(n)	❌ Non richiesto
Ricerca Binaria	O(1)	O(log n)	O(log n)	✅ Obbligatorio

💡 Quando usare quale Se l'array non è ordinato (e ordinarlo sarebbe costoso): usa la ricerca lineare. Se l'array è già ordinato o verrà cercato molte volte: ordina una volta e usa sempre la binaria — il costo di ordinamento è ammortizzato su tutte le ricerche successive.

⚠ Il caso migliore O(1) Entrambi hanno caso migliore O(1): la lineare se il target è in posizione 0, la binaria se è esattamente al centro. Nella pratica il caso migliore è irrilevante — si progetta sempre per il caso peggiore.