Algoritmus vyhledávání více položek (Multiple-Item Search) v C++- vysvětlení, příklad a kód

Algoritmus vyhledávání více položek se používá k nalezení všech výskytů určitého prvku v seznamu. Na rozdíl od jednopoložkových vyhledávacích algoritmů tento přístup sleduje vícenásobné výskyty cílového prvku a vrací seznam jejich pozic.

Jak to funguje

1. Začněte od začátku seznamu.
2. Iterujte každý prvek v seznamu.
3. Porovnejte aktuální prvek s cílovou hodnotou.
4. Pokud se aktuální prvek rovná cílové hodnotě, zaznamenejte jeho polohu.
5. Pokračujte na další prvek a opakujte kroky 3-4.
6. Po iteraci celého seznamu vraťte seznam zaznamenaných pozic.

Příklad

Uvažujme seznam celých čísel a chceme najít všechny výskyty čísla 23.

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

1. Začněte od začátku: 12. Není požadované číslo.
2. Přejít na další prvek: 23. Shoda nalezena, zaznamenejte pozici 1.
3. Přejděte na další prvek: 45. Není požadované číslo.
4. Přejít na další prvek: 23. Shoda nalezena, zaznamenejte pozici 3.
5. Přejděte na další prvek: 56. Není požadované číslo.
6. Přejít na další prvek: 23. Shoda nalezena, zaznamenejte pozici 5.
7. Přejděte na další prvek: 89. Není požadované číslo.
8. Přejděte na další prvek: 90. Není požadované číslo.
9. Po iteraci vraťte seznam pozic: [1, 3, 5].

Příklad kódu v 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;  
}  

V uvedeném příkladu multipleItemSearch je funkce použita k nalezení všech výskytů čísla 23 v seznamu celých čísel. Výsledkem bude vektor obsahující pozice všech výskytů(pozice začínají od 0).