Algoritmo di ricerca lineare (Linear Search) in C++- Spiegazione, esempio e codice

L'algoritmo di ricerca lineare è un metodo semplice utilizzato per trovare un elemento specifico in un elenco. Questo algoritmo funziona controllando in sequenza ogni elemento nell'elenco fino a quando non viene trovato l'elemento desiderato o viene attraversato l'intero elenco.

Come funziona

1. Inizia dal primo elemento nell'elenco.
2. Confronta l'elemento corrente con il valore di destinazione.
3. Se l'elemento corrente è uguale al valore di destinazione, l'algoritmo termina e restituisce la posizione dell'elemento.
4. In caso contrario, continua a scorrere gli elementi rimanenti nell'elenco.
5. Se l'intero elenco viene attraversato senza trovare l'elemento di destinazione, l'algoritmo restituisce un valore che indica non trovato.

Esempio

Diciamo che abbiamo un elenco di numeri interi e vogliamo trovare il numero 34 nell'elenco.

Elenco: {12, 45, 67, 89, 34, 56, 23, 90}

1. Inizia dal primo elemento: 12. Non è il numero desiderato.
2. Passa all'elemento successivo: 45. Non è il numero desiderato.
3. Continua con gli elementi rimanenti: 67, 89, 34. L'elemento 34 corrisponde al numero desiderato.
4. L'algoritmo termina e restituisce la posizione di 34, che è 4.

Esempio di codice in C++

#include <iostream>  
#include <vector>  
  
int linearSearch(const std::vector<int>& arr, int target) {  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            return i;  
        }  
    }  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 45, 67, 89, 34, 56, 23, 90};  
    int target = 34;  
  
    int result = linearSearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

Nell'esempio dato, abbiamo utilizzato la linearSearch funzione per trovare il numero 34 nell'elenco dei numeri interi. Il risultato sarà la posizione 34 nell'elenco(le posizioni iniziano da 0) o -1 se il numero non viene trovato.