Lineær søkealgoritme (Linear Search) i C++- Forklaring, eksempel og kode

Den lineære søkealgoritmen er en enkel metode som brukes til å finne et spesifikt element i en liste. Denne algoritmen fungerer ved å sekvensielt sjekke hvert element i listen til det ønskede elementet er funnet eller hele listen er krysset.

Hvordan det fungerer

1. Start fra det første elementet i listen.
2. Sammenlign gjeldende element med målverdien.
3. Hvis det gjeldende elementet er lik målverdien, avsluttes algoritmen og returnerer posisjonen til elementet.
4. Hvis ikke, fortsett å iterere gjennom de gjenværende elementene i listen.
5. Hvis hele listen krysses uten å finne målelementet, returnerer algoritmen en verdi som indikerer ikke funnet.

Eksempel

La oss si at vi har en liste over heltall og vi ønsker å finne tallet 34 i listen.

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

1. Start ved det første elementet: 12. Ikke ønsket tall.
2. Gå til neste element: 45. Ikke ønsket tall.
3. Fortsett med de resterende elementene: 67, 89, 34. Element 34 samsvarer med ønsket tall.
4. Algoritmen avslutter og returnerer posisjonen til 34, som er 4.

Eksempelkode i C++

#include <iostream>  
#include <vector>  
  
int linearSearch(const std::vector<int>& arr, int target) {  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            return i;  
        }  
    }  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 45, 67, 89, 34, 56, 23, 90};  
    int target = 34;  
  
    int result = linearSearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

I det gitte eksemplet har vi brukt linearSearch funksjonen til å finne tallet 34 i listen over heltall. Resultatet vil være posisjonen 34 i listen(posisjonene starter fra 0) eller -1 hvis tallet ikke finnes.