Algorytm wyszukiwania wielu elementów (Multiple-Item Search) w C++- wyjaśnienie, przykład i kod

Algorytm wyszukiwania wielu elementów służy do znajdowania wszystkich wystąpień określonego elementu na liście. W przeciwieństwie do algorytmów wyszukiwania pojedynczego elementu, to podejście śledzi wiele wystąpień elementu docelowego i zwraca listę jego pozycji.

Jak to działa

1. Zacznij od początku listy.
2. Iteruj przez każdy element na liście.
3. Porównaj bieżący element z wartością docelową.
4. Jeśli bieżący element jest równy wartości docelowej, zapisz jego pozycję.
5. Przejdź do następnego elementu i powtórz kroki 3-4.
6. Po iteracji przez całą listę zwróć listę zarejestrowanych pozycji.

Przykład

Rozważmy listę liczb całkowitych i chcemy znaleźć wszystkie wystąpienia liczby 23.

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

1. Zacznij od początku: 12. Nie żądana liczba.
2. Przejdź do następnego elementu: 23. Znaleziono dopasowanie, zapisz pozycję jako 1.
3. Przejdź do następnego elementu: 45. Nie żądana liczba.
4. Przejdź do następnego elementu: 23. Znaleziono dopasowanie, zapisz pozycję jako 3.
5. Przejdź do następnego elementu: 56. Nie żądana liczba.
6. Przejdź do następnego elementu: 23. Znaleziono dopasowanie, zapisz pozycję jako 5.
7. Przejdź do następnego elementu: 89. Nie żądana liczba.
8. Przejdź do następnego elementu: 90. Nie żądana liczba.
9. Po iteracji zwróć listę pozycji: [1, 3, 5].

Przykładowy kod w 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;  
}  

W podanym przykładzie multipleItemSearch funkcja służy do znalezienia wszystkich wystąpień liczby 23 na liście liczb całkowitych. Wynikiem będzie wektor zawierający pozycje wszystkich wystąpień(pozycje zaczynają się od 0).