· 

Die lineare Suche

1. Einführung

In meinem Artikel zur binären Suche habe ich einen naiven Algorithmus angesprochen, mit dem man ebenfalls Elemente in einer Liste suchen kann. Dabei handelt es sich um die sogenannte lineare Suche, die gleichzeitig den einfachsten Suchalgorithmus darstellt.

Bevor wir uns den Algorithmus formal anschauen, überlegen wir uns, wie die naivste Suche nach einem Element in einer (un)sortierten Liste aussehen kann. Man geht einfach jedes Element nacheinander durch und prüft, ob das gesuchte Element dabei ist. Wenn das gesuchte Element dabei ist, notiert man sich die Position von dem Element in der Liste. Falls es nicht dabei ist, notiert man sich, dass das gesuchte Element nicht in der Liste gefunden wurde. Und das ist im Prinzip schon der Algorithmus.

2. Der Algorithmus

Um ihn später implementieren zu können, versuchen wir den Algorithmus noch einmal formal zu definieren.
Algorithmus: Lineare Suche

Eingabe: (Un-)sortierte Liste \(L\) mit \(n\) Elementen, gesuchtes Element \(e\).
Ausgabe: Index \(i\) des gesuchten Elements \(e\). Falls das Element nicht gefunden wurde, wird ein Fluchtwert (z. B. \(-1\)) zurückgegeben.
  1. Beginne beim ersten Element (\(i=0\)).
    • Wenn das Element mit dem Index \(i\) dem Element \(e\) entspricht, gib den Index \(i\) zurück und gehe zu Schritt 4.
    • Wenn das Element mit dem Index \(i\) nicht dem Element \(e\) entspricht, gehe zum nächsten Element (\(i=i+1\)).
  2. Wenn du am Ende der Liste (\(i=n-1\)) angekommen bist und \(e\) nicht gefunden hast, gib den Fluchtwert \(-1\) zurück und gehe zu Schritt 4.
  3. Beende den Algorithmus.

3. Beispiele

Als Beispiel betrachten wir die Liste $$1, 17, 6, 8, 22, 13, 40, 33$$ Gesucht sei das Element \(e=6\).
  • Wir beginnen beim ersten Element der Liste mit dem Index \(i=0\), nämlich der \(1\). Da \(1\neq 6\) ist, setzen wir den Index auf \(i=0+1=1\).
  • Das Element mit dem Index \(i=1\) ist \(17\). Da \(17\neq 6\) ist, setzen wir den Index auf \(i=1+1=2\).
  • Das Element mit dem Index \(i=2\) ist \(6\). Da \(6=6\) das gesuchte Element ist, geben wir den Index \(i=2\) als Ausgabe zurück.
Als weiteres Beispiel betrachten wir erneut die Liste $$1, 17, 6, 8, 22, 13, 40, 33$$ und suchen diesmal aber das Element \(42\).
  • Wir beginnen beim ersten Element der Liste mit dem Index \(i=0\), nämlich der \(1\). Da \(1\neq 42\) ist, setzen wir den Index auf \(i=0+1=1\).
  • Das Element mit dem Index \(i=1\) ist \(17\). Da \(17\neq 42\) ist, setzen wir den Index auf \(i=1+1=2\).
  • Das Element mit dem Index \(i=2\) ist \(6\). Da \(6\neq 42\) ist, setzen wir den Index auf \(i=2+1=3\).
  • Das Element mit dem Index \(i=3\) ist \(8\). Da \(8\neq 42\) ist, setzen wir den Index auf \(i=3+1=4\).
  • ...
  • Das Element mit dem Index \(i=7\) ist \(33\). Da \(33\neq 42\) ist und wir am Ende der Liste angekommen sind, geben wir als Fluchtwert \(-1\) zurück, um zu zeigen, dass \(42\) nicht in der zu dursuchenden Liste ist.

4. Laufzeit

In den vorangegangenen Beispielen hast du bereits gesehen, dass es einen großen Unterschied macht, wo die einzelnen Elemente in der Liste stehen. Je weiter hinten das gesuchte Element ist, desto länger muss der Algorithmus laufen.
  • Wenn das gesuchte Element überhaupt nicht in der Liste auftaucht, müssen alle Elemente durchlaufen und geprüft werden.
  • Das beschreibt den sogenannten Worst Case (also den schlimmsten anzunehmenden Fall).
  • Für den Fall, dass die Elemente in der Liste zufällig verteilt sind, braucht man durchschnittlich $$\frac{n+1}{2}$$ Vergleichsoperationen. D. h. wenn du eine Liste mit \(49\) zufällig verteilten Elementen hast, brauchst du voraussichtlich um die \(25\) Versuche mit der linearen Suche, wenn du dich von Vorne nach Hinten durcharbeitest.
  • Im besten Fall steht das gesuchte Element direkt am Anfang der Liste. Dann brauchst du nur eine Vergleichsoperation. Das ist der sogenannte Best Case (also der beste anzunehmende Fall für das Ausgangsproblem).
Da die Laufzeit (wie der Name des Algorithmus schon vermuten lässt) linear mit der Anzahl an Elementen in der zu durchsuchenden Liste steigt, liegt sie in \(\mathcal{O}(n)\), also weniger performant als die binäre Suche, deren Laufzeit in \(\mathcal{O}(\log_2(n))\) liegt. Allerdings funktioniert die binäre Suche nur für sortierte Listen, d. h. bei einer unsortierten Liste müsste man diese zunächst mit einem Sortieralgorithmus sortieren.
Wenn die Liste unsortiert ist, gibt es Algorithmen (wie etwa Lazy Select), die mit dem Zufall arbeiten und mit einer bestimmten Wahrscheinlichkeit laufzeittechnisch besser als die lineare Suche performen. Du kannst dir mal ein Programm schreiben, das zufällig in einer gegebenen Liste sucht und die Anzahl an Vergleichsoperationen mit denen der linearen Suche vergleichen. Apropos Programm schreiben: Wir werden uns jetzt mit der Implementierung der linearen Suche beschäftigen.

5. Implementierung

Die Implementierung des Algorithmus ist denkbar einfach. Hierfür sind lediglich eine einfache for-Schleife zum Durchlaufen der Listenelemente und eine If-Abfrage notwendig. Eine Implementierung in C++ könnte folgendermaßen aussehen:
Zunächst wird eine Funktion mit z. B. dem Namen linear_search definiert. Als Übergabe erhält diese Funktion eine Liste mit Elementen (in Form eines Arrays) und ein Element, das innerhalb der Liste gesucht werden soll.
int linear_search(int list[], int e)
Als nächstes durchläufst du in einer for-Schleife die einzelnen Listenelemente und prüfst, ob das aktuelle Listenelement dem gesuchten Element entspricht. Wenn das der Fall ist, gibst du den Index zurück, an dem sich das Element befindet.
for(int i = 0; i < sizeof(list); i++){
    if(list[i] == e){
        return i;
    }
}
Wenn du am Ende der for-Schleife angekommen bist und das Element nicht gefunden wurde, gibst du den Wert \(-1\) zurück, um zu signalisieren, dass das gesuchte Element nicht in der Liste gefunden wurde.
return -1;
Der Aufruf im Programm sieht dann wie folgt aus:
int main(){
    int list[] = {1,2,4,5,18};
    std::cout << linear_search(list, 5);
}
Das Programm liefert als Ausgabe \(3\), da das Element \(5\) an der vierten Stelle in der Liste steht. Der Aufruf
int main(){
    int list[] = {1,2,4,5,18};
    std::cout << linear_search(list, 42);
}
führt zur Ausgabe \(-1\), da \(42\) nicht in der Liste enthalten ist.

6. Quellcode

#include <iostream>
#include <string>

int linear_search(int list[], int e){
    for(int i = 0; i < sizeof(list); i++){
        if(list[i] == e){
            return i;
        }
    }
    return -1;
}

int main(){
    int list[] = {1,2,4,5,18};
    std::cout << linear_search(list, 42);
}