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

Den lineære søgealgoritme er en simpel metode, der bruges til at finde et bestemt element i en liste. Denne algoritme fungerer ved sekventielt at kontrollere hvert element i listen, indtil det ønskede element er fundet, eller hele listen gennemløbes.

Hvordan det virker

1. Start fra det første element på listen.
2. Sammenlign det aktuelle element med målværdien.
3. Hvis det aktuelle element er lig med målværdien, afsluttes algoritmen og returnerer elementets position.
4. Hvis ikke, fortsæt med at iterere gennem de resterende elementer på listen.
5. Hvis hele listen gennemløbes uden at finde målelementet, returnerer algoritmen en værdi, der indikerer ikke fundet.

Eksempel

Lad os sige, at vi har en liste over heltal, og vi vil finde tallet 34 på listen.

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

1. Start ved det første element: 12. Ikke det ønskede tal.
2. Flyt til næste element: 45. Ikke det ønskede tal.
3. Fortsæt med de resterende elementer: 67, 89, 34. Element 34 matcher det ønskede tal.
4. Algoritmen afslutter og returnerer positionen 34, hvilket 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 givne eksempel har vi brugt linearSearch funktionen til at finde tallet 34 på listen over heltal. Resultatet vil være positionen 34 på listen(positionerne starter fra 0) eller -1, hvis tallet ikke findes.