close

Algorithme de recherche à éléments multiples (Multiple-Item Search) en C++- Explication, exemple et code

L'algorithme de recherche d'éléments multiples est utilisé pour trouver toutes les occurrences d'un élément spécifique dans une liste. Contrairement aux algorithmes de recherche à élément unique, cette approche garde une trace de plusieurs occurrences de l'élément cible et renvoie une liste de leurs positions.

Comment ça fonctionne

  1. Commencez par le début de la liste.
  2. Parcourez chaque élément de la liste.
  3. Comparez l'élément actuel avec la valeur cible.
  4. Si l'élément actuel est égal à la valeur cible, enregistrez sa position.
  5. Passez à l'élément suivant et répétez les étapes 3-4.
  6. Après avoir parcouru toute la liste, retournez la liste des positions enregistrées.

Exemple

Considérons une liste d'entiers et nous voulons trouver toutes les occurrences du nombre 23.

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

  1. Recommencer depuis le début : 12. Pas le nombre souhaité.
  2. Passer à l'élément suivant: 23. Correspondance trouvée, enregistrer la position comme 1.
  3. Passer à l'élément suivant : 45. Pas le nombre souhaité.
  4. Passer à l'élément suivant : 23. Correspondance trouvée, enregistrer la position comme 3.
  5. Passer à l'élément suivant : 56. Pas le nombre souhaité.
  6. Passez à l'élément suivant : 23. Correspondance trouvée, enregistrez la position comme 5.
  7. Passer à l'élément suivant : 89. Pas le nombre souhaité.
  8. Passer à l'élément suivant : 90. Pas le nombre souhaité.
  9. Après itération, renvoie une liste de positions : [1, 3, 5].

Exemple de code en 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;  
}

Dans l'exemple donné, la multipleItemSearch fonction est utilisée pour trouver toutes les occurrences du nombre 23 dans une liste d'entiers. Le résultat sera un vecteur contenant les positions de toutes les occurrences(les positions commencent à 0).