close

Алгоритм поиска по нескольким элементам (Multiple-Item Search) в C++ — объяснение, пример и код

Алгоритм поиска по нескольким элементам используется для поиска всех вхождений определенного элемента в списке. В отличие от алгоритмов поиска по одному элементу, этот подход отслеживает несколько вхождений целевого элемента и возвращает список их позиций.

Как это работает

  1. Начните с начала списка.
  2. Перебрать каждый элемент в списке.
  3. Сравните текущий элемент с целевым значением.
  4. Если текущий элемент равен целевому значению, запишите его позицию.
  5. Перейдите к следующему элементу и повторите шаги 3-4.
  6. После перебора всего списка верните список записанных позиций.

Пример

Давайте рассмотрим список целых чисел, и мы хотим найти все вхождения числа 23.

Список: {12, 23, 45, 23, 56, 23, 89, 90}

  1. Начать сначала: 12. Не нужное число.
  2. Перейти к следующему элементу: 23. Совпадение найдено, запишите позицию как 1.
  3. Перейти к следующему элементу: 45. Не нужное число.
  4. Перейти к следующему элементу: 23. Совпадение найдено, запишите позицию как 3.
  5. Перейти к следующему элементу: 56. Не нужное число.
  6. Перейти к следующему элементу: 23. Совпадение найдено, запишите позицию как 5.
  7. Перейти к следующему элементу: 89. Не нужное число.
  8. Перейти к следующему элементу: 90. Не нужное число.
  9. После итерации верните список позиций: [1, 3, 5].

Пример кода на С++ 

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

В данном примере multipleItemSearch функция используется для поиска всех вхождений числа 23 в список целых чисел. Результатом будет вектор, содержащий позиции всех вхождений(позиции начинаются с 0).