close

Zoekalgoritme met meerdere items (Multiple-Item Search) in C ++- uitleg, voorbeeld en code

Het zoekalgoritme met meerdere items wordt gebruikt om alle exemplaren van een specifiek element in een lijst te vinden. In tegenstelling tot zoekalgoritmen voor één item, houdt deze benadering meerdere keren dat het doelelement voorkomt bij en retourneert een lijst met hun posities.

Hoe het werkt

  1. Begin bij het begin van de lijst.
  2. Doorloop elk element in de lijst.
  3. Vergelijk het huidige element met de doelwaarde.
  4. Als het huidige element gelijk is aan de doelwaarde, noteer dan de positie ervan.
  5. Ga door naar het volgende element en herhaal stap 3-4.
  6. Na het herhalen van de volledige lijst, retourneert u de lijst met geregistreerde posities.

Voorbeeld

Laten we eens kijken naar een lijst met gehele getallen en we willen alle voorkomens van het getal 23 vinden.

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

  1. Begin bij het begin: 12. Niet het gewenste aantal.
  2. Ga naar het volgende element: 23. Match gevonden, noteer positie als 1.
  3. Ga naar het volgende element: 45. Niet het gewenste aantal.
  4. Ga naar het volgende element: 23. Match gevonden, noteer positie als 3.
  5. Ga naar het volgende element: 56. Niet het gewenste nummer.
  6. Ga naar het volgende element: 23. Match gevonden, noteer positie als 5.
  7. Ga naar het volgende element: 89. Niet het gewenste aantal.
  8. Ga naar het volgende element: 90. Niet het gewenste aantal.
  9. Retourneer na iteratie een lijst met posities: [1, 3, 5].

Voorbeeldcode 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;  
}

In het gegeven voorbeeld multipleItemSearch wordt de functie gebruikt om alle voorkomens van het getal 23 in een lijst met gehele getallen te vinden. Het resultaat is een vector die de posities van alle voorkomens bevat(posities beginnen bij 0).