close

Søkealgoritme med flere elementer (Multiple-Item Search) i C++- Forklaring, eksempel og kode

Søkealgoritmen med flere elementer brukes til å finne alle forekomster av et spesifikt element i en liste. I motsetning til enkeltelementsøkealgoritmer, holder denne tilnærmingen oversikt over flere forekomster av målelementet og returnerer en liste over deres posisjoner.

Hvordan det fungerer

  1. Start fra begynnelsen av listen.
  2. Iterer gjennom hvert element i listen.
  3. Sammenlign gjeldende element med målverdien.
  4. Hvis det gjeldende elementet er lik målverdien, registrerer du dets posisjon.
  5. Fortsett til neste element og gjenta trinn 3-4.
  6. Etter å ha gjentatt hele listen, returner listen over registrerte posisjoner.

Eksempel

La oss vurdere en liste over heltall, og vi vil finne alle forekomster av tallet 23.

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

  1. Start fra begynnelsen: 12. Ikke ønsket antall.
  2. Gå til neste element: 23. Match funnet, registrer posisjon som 1.
  3. Gå til neste element: 45. Ikke ønsket tall.
  4. Gå til neste element: 23. Match funnet, registrer posisjon som 3.
  5. Gå til neste element: 56. Ikke ønsket tall.
  6. Gå til neste element: 23. Match funnet, registrer posisjon som 5.
  7. Gå til neste element: 89. Ikke ønsket tall.
  8. Gå til neste element: 90. Ikke ønsket tall.
  9. Etter iterasjon, returner en liste over posisjoner: [1, 3, 5].

Eksempelkode i 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;  
}

I det gitte eksemplet multipleItemSearch brukes funksjonen til å finne alle forekomster av tallet 23 i en liste over heltall. Resultatet vil være en vektor som inneholder posisjonene til alle forekomster(posisjoner starter fra 0).