Lineare Suche

Grundprinzip und Einsatz

Die lineare Suche, auch sequentielle Suche genannt, ist der einfachste Suchalgorithmus. Sie sucht ein bestimmtes Element in einer Liste oder einem Array mit n Elementen. Dazu werden die Elemente der Reihe nach mit dem Suchschlüssel, also dem gesuchten Wert, verglichen. Die Suche endet gewöhnlich beim ersten Treffer oder nach dem letzten Element, falls der Wert nicht vorkommt.

Die lineare Suche funktioniert auch bei ungeordneten Listen. Die effizientere binäre Suche setzt dagegen eine geordnete Liste voraus. Für kleine Listen ist die lineare Suche oft das effizienteste Verfahren. Für ungeordnete Listen gibt es außerdem Lazy Select, einen randomisierten Algorithmus, der mit relativ hoher Wahrscheinlichkeit das x-te Element bezüglich einer Ordnung schneller als in linearer Zeit finden kann.

Laufzeit und Anzahl der Vergleiche

Der Suchaufwand wächst linear mit der Zahl n der Listenelemente. Deshalb gehört der Algorithmus zur Komplexitätsklasse O(n).

• Schlechtester Fall: Der gesuchte Wert ist nicht vorhanden oder wird erst am Ende gefunden. Dann sind n Vergleiche nötig.

• Durchschnitt bei zufallsverteilten Daten: Es werden (n+1)/2 Vergleichsoperationen benötigt.

• Bester Fall: Bereits das erste Element ist der gesuchte Wert; dann genügt ein Vergleich.

Allgemeiner Ablauf

Der Algorithmus erhält einen Suchschlüssel S und ein Array A. Zunächst wird die Anzahl N der Elemente bestimmt, der Startindex i auf 0 gesetzt und der Sucherfolg als falsch markiert. Anschließend werden die Elemente nacheinander geprüft. Gilt A[i] = S, wird die Suche als erfolgreich markiert. Bei Erfolg wird der Index i ausgegeben; andernfalls lautet das Ergebnis, dass die Suche nicht erfolgreich war.

Mögliche Rückgabewerte

Die Beispielimplementierungen unterscheiden sich vor allem darin, welches Ergebnis sie liefern:

• C, Java sowie Delphi beziehungsweise Free Pascal geben bei einem Treffer einen Index zurück und verwenden -1 für „nicht gefunden“.

• Ruby liefert den Index des ersten Treffers und andernfalls nil; alternativ kann die eingebaute Methode index verwendet werden.

• Objective CAML liefert einen Wahrheitswert: true bei einem Treffer und false, wenn der Wert nicht vorkommt.

• Python zeigt zwei Varianten: Eine sammelt die Indizes aller Vorkommen in einer Liste. Die andere beendet die Suche beim ersten Vorkommen und liefert dessen Index; wenn nichts gefunden wird, kann sie None zurückgeben.

Ob nur das erste oder alle Vorkommen ermittelt werden, hängt somit von der konkreten Implementierung ab.

Typisches Beispiel

Im C-Beispiel wird das Array [81, 1203, 180, 42, 10, 566, 102, 751, 54, 648] nach dem Wert 42 durchsucht. Die Vergleiche beginnen beim Index 0. Der Wert 42 wird am Index 3 gefunden, wobei die Indizierung mit 0 beginnt. Die Funktion gibt daher 3 zurück. Wäre der Wert nicht vorhanden, würde sie -1 zurückgeben.