close

Algoritmo di ricerca di più elementi (Multiple-Item Search) in C++: spiegazione, esempio e codice

L'algoritmo di ricerca a più elementi viene utilizzato per trovare tutte le occorrenze di un elemento specifico in un elenco. A differenza degli algoritmi di ricerca a elemento singolo, questo approccio tiene traccia di più occorrenze dell'elemento di destinazione e restituisce un elenco delle loro posizioni.

Come funziona

  1. Inizia dall'inizio dell'elenco.
  2. Scorri ogni elemento nell'elenco.
  3. Confronta l'elemento corrente con il valore di destinazione.
  4. Se l'elemento corrente è uguale al valore target, registrane la posizione.
  5. Continua con l'elemento successivo e ripeti i passaggi 3-4.
  6. Dopo aver ripetuto l'intero elenco, restituire l'elenco delle posizioni registrate.

Esempio

Consideriamo un elenco di numeri interi e vogliamo trovare tutte le occorrenze del numero 23.

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

  1. Inizia dall'inizio: 12. Non è il numero desiderato.
  2. Passa all'elemento successivo: 23. Corrispondenza trovata, registra la posizione come 1.
  3. Passa all'elemento successivo: 45. Non è il numero desiderato.
  4. Passa all'elemento successivo: 23. Corrispondenza trovata, registra la posizione come 3.
  5. Passa all'elemento successivo: 56. Non è il numero desiderato.
  6. Passa all'elemento successivo: 23. Corrispondenza trovata, registra la posizione come 5.
  7. Passa all'elemento successivo: 89. Non è il numero desiderato.
  8. Passa all'elemento successivo: 90. Non è il numero desiderato.
  9. Dopo l'iterazione, restituire un elenco di posizioni: [1, 3, 5].

Esempio di codice in C++ 

#include <iostream>  
#include <vector>  
  
std::vector<int> multipleItemSearch(const std::vector<int>& arr, int target) {  
    std::vector<int> positions;  
  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 45, 23, 56, 23, 89, 90};  
    int target = 23;  
  
    std::vector<int> result = multipleItemSearch(numbers, target);  
  
    std::cout << "Occurrences of " << target << " found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

Nell'esempio fornito, la multipleItemSearch funzione viene utilizzata per trovare tutte le occorrenze del numero 23 in un elenco di numeri interi. Il risultato sarà un vettore contenente le posizioni di tutte le occorrenze(le posizioni iniziano da 0).