close

Algoritmo de búsqueda de elementos múltiples (Multiple-Item Search) en C++: explicación, ejemplo y código

El algoritmo de búsqueda de elementos múltiples se utiliza para encontrar todas las apariciones de un elemento específico en una lista. A diferencia de los algoritmos de búsqueda de un solo elemento, este enfoque realiza un seguimiento de las múltiples apariciones del elemento de destino y devuelve una lista de sus posiciones.

Cómo funciona

  1. Comience desde el principio de la lista.
  2. Iterar a través de cada elemento de la lista.
  3. Compare el elemento actual con el valor objetivo.
  4. Si el elemento actual es igual al valor objetivo, registre su posición.
  5. Continúe con el siguiente elemento y repita los pasos 3 y 4.
  6. Después de recorrer toda la lista, devuelva la lista de posiciones registradas.

Ejemplo

Consideremos una lista de números enteros y queremos encontrar todas las ocurrencias del número 23.

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

  1. Comience desde el principio: 12. No es el número deseado.
  2. Pasar al siguiente elemento: 23. Coincidencia encontrada, registrar la posición como 1.
  3. Pasa al siguiente elemento: 45. No es el número deseado.
  4. Pase al siguiente elemento: 23. Coincidencia encontrada, registre la posición como 3.
  5. Pasar al siguiente elemento: 56. No es el número deseado.
  6. Pase al siguiente elemento: 23. Coincidencia encontrada, registre la posición como 5.
  7. Pasa al siguiente elemento: 89. No es el número deseado.
  8. Pasa al siguiente elemento: 90. No es el número deseado.
  9. Después de iterar, devuelva una lista de posiciones: [1, 3, 5].

Código de ejemplo 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;  
}

En el ejemplo dado, la multipleItemSearch función se usa para encontrar todas las apariciones del número 23 en una lista de enteros. El resultado será un vector que contiene las posiciones de todas las ocurrencias(las posiciones comienzan desde 0).