Ricerca lineare in array con ciclo ottimizzato

Ricerca Lineare (Sequenziale)

Cos'è la ricerca lineare?

La ricerca lineare è uno degli algoritmi più semplici per trovare un elemento all'interno di un array. Funziona controllando ogni elemento dell'array uno dopo l'altro, dalla prima posizione fino all'ultima, finché non trova l'elemento cercato o finisce gli elementi da controllare.

Analisi del codice

Vediamo come funziona questo programma passo per passo:

Dichiarazione delle variabili

int a[10] = {7, 3, 9, 1, 5};
int n = 5;
int valore = 9;                  // valore cercato
int trovato = -1;                // -1 = non trovato

• a[10]: un array di 10 posizioni, ma riempiamo solo le prime 5 con i valori {7, 3, 9, 1, 5}
• n = 5: indica quanti elementi dell'array sono effettivamente utilizzati
• valore = 9: è il numero che stiamo cercando nell'array
• trovato = -1: questa variabile memorizza la posizione dove troviamo l'elemento. Inizialmente è -1 per indicare "non trovato"

Il ciclo di ricerca

for (int i = 0; i < n && trovato == -1; i++)
    if (a[i] == valore)
        trovato = i;

Questo ciclo è il cuore dell'algoritmo:

• i = 0: iniziamo dalla prima posizione dell'array (posizione 0)
• i < n: continuiamo finché non abbiamo controllato tutti gli elementi
• trovato == -1: condizione intelligente! Il ciclo si ferma anche se troviamo l'elemento, perché trovato non sarà più uguale a -1
• if (a[i] == valore): se l'elemento nella posizione i è uguale al valore cercato
• trovato = i: salviamo la posizione dove abbiamo trovato l'elemento

Visualizzazione dell'esecuzione

Vediamo cosa succede passo per passo cercando il valore 9:

Il ciclo si ferma qui perché trovato non è più uguale a -1!

Stampa del risultato

if (trovato != -1)
    cout << "Il valore " << valore << " e' in posizione " << trovato << endl;
else
    cout << "Il valore " << valore << " non e' presente" << endl;

• Se trovato è diverso da -1, significa che abbiamo trovato l'elemento e stampiamo la sua posizione
• Altrimenti stampiamo che l'elemento non è presente nell'array

Caratteristiche dell'algoritmo

Vantaggi:

• Semplice da capire e implementare
• Funziona su array non ordinati
• Si ferma appena trova l'elemento (grazie alla condizione trovato == -1)

Svantaggi:

• Può essere lento per array molto grandi
• Nel caso peggiore deve controllare tutti gli elementi

Risultato del programma

Eseguendo questo codice, l'output sarà:

Il valore 9 e' in posizione 2

Ricorda che in informatica si conta sempre da 0, quindi la posizione 2 corrisponde al terzo elemento dell'array!

// RICERCA LINEARE (sequenziale)
#include <iostream>
using namespace std;

int main() {
    int a[10] = {7, 3, 9, 1, 5};
    int n = 5;
    int valore = 9;                  // valore cercato
    int trovato = -1;                // -1 = non trovato

    // il ciclo si ferma appena trovato diventa diverso da -1
    for (int i = 0; i < n && trovato == -1; i++)
        if (a[i] == valore)
            trovato = i;

    if (trovato != -1)
        cout << "Il valore " << valore << " e' in posizione " << trovato << endl;
    else
        cout << "Il valore " << valore << " non e' presente" << endl;

    return 0;
}