Lineair zoekalgoritme (Linear Search) in C++- uitleg, voorbeeld en code

Het lineaire zoekalgoritme is een eenvoudige methode om een ​​specifiek element in een lijst te vinden. Dit algoritme werkt door achtereenvolgens elk element in de lijst te controleren totdat het gewenste element is gevonden of de hele lijst is doorlopen.

Hoe het werkt

1. Begin bij het eerste element in de lijst.
2. Vergelijk het huidige element met de doelwaarde.
3. Als het huidige element gelijk is aan de doelwaarde, wordt het algoritme beëindigd en wordt de positie van het element geretourneerd.
4. Als dit niet het geval is, gaat u door met het herhalen van de resterende elementen in de lijst.
5. Als de hele lijst wordt doorlopen zonder het doelelement te vinden, retourneert het algoritme een waarde die aangeeft niet gevonden.

Voorbeeld

Laten we zeggen dat we een lijst met gehele getallen hebben en we willen het getal 34 in de lijst vinden.

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

1. Begin bij het eerste element: 12. Niet het gewenste aantal.
2. Ga naar het volgende element: 45. Niet het gewenste aantal.
3. Ga verder met de resterende elementen: 67, 89, 34. Element 34 komt overeen met het gewenste aantal.
4. Het algoritme beëindigt en retourneert de positie van 34, wat 4 is.

Voorbeeldcode in 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;  
}  

In het gegeven voorbeeld hebben we de linearSearch functie gebruikt om het getal 34 te vinden in de lijst met gehele getallen. Het resultaat is de positie van 34 in de lijst(posities beginnen vanaf 0) of -1 als het nummer niet wordt gevonden.