close

Linearer Suchalgorithmus (Linear Search) in C++ – Erklärung, Beispiel und Code

Der lineare Suchalgorithmus ist eine einfache Methode, um ein bestimmtes Element in einer Liste zu finden. Bei diesem Algorithmus wird nacheinander jedes Element in der Liste überprüft, bis das gewünschte Element gefunden oder die gesamte Liste durchlaufen wird.

Wie es funktioniert

  1. Beginnen Sie mit dem ersten Element in der Liste.
  2. Vergleichen Sie das aktuelle Element mit dem Zielwert.
  3. Wenn das aktuelle Element dem Zielwert entspricht, wird der Algorithmus beendet und die Position des Elements zurückgegeben.
  4. Wenn nicht, iterieren Sie weiter durch die verbleibenden Elemente in der Liste.
  5. Wenn die gesamte Liste durchlaufen wird, ohne dass das Zielelement gefunden wird, gibt der Algorithmus einen Wert zurück, der angibt, dass er nicht gefunden wurde.

Beispiel

Nehmen wir an, wir haben eine Liste mit ganzen Zahlen und möchten die Zahl 34 in der Liste finden.

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

  1. Beginnen Sie mit dem ersten Element: 12. Nicht die gewünschte Zahl.
  2. Zum nächsten Element wechseln: 45. Nicht die gewünschte Zahl.
  3. Fahren Sie mit den restlichen Elementen fort: 67, 89, 34. Element 34 entspricht der gewünschten Zahl.
  4. Der Algorithmus terminiert und gibt die Position 34 zurück, also 4.

Beispielcode 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;  
}

Im gegebenen Beispiel haben wir die linearSearch Funktion verwendet, um die Zahl 34 in der Liste der ganzen Zahlen zu finden. Das Ergebnis ist die Position 34 in der Liste(Positionen beginnen bei 0) oder -1, wenn die Nummer nicht gefunden wird.