Lineare Suche

Lineare Suche ist ein Algorithmus. Er ist auch unter dem Namen Sequenzielle Suche bekannt. Er ist der einfachste Suchalgorithmus überhaupt.

Die Aufgabe besteht darin ein Element in einer Liste oder einem Array zu finden. Man geht die Liste Element für Element durch, bis man es gefunden hat. Der Suchaufwand wächst linear mit der Anzahl Elemente in der Liste.

Wenn die Daten zufallsverteilt sind, dann werden im Schnitt N/2 Vergleichsoperationen benötigt. Im besten Fall ist gleich das erste Element der Liste dasjenige, das man sucht, im schlechtesten ist es das Letzte.

Beispielimplementation in Ruby:

def Lineare_suche(datenArray,wert)
    for i in datenArray
        return true if i == wert;
    end
    return false
end

Lineare Suche kann immer verwendet werden. Wenn die Anzahl Element in einer Liste klein ist, dann ist es oft auch das effizienteste Verfahren.

Die effizientere Binäre Suche kann nur bei geordnete Listen benutzt werden. Für ungeordnete Listen existiert mit Lazy Select noch ein randomisierter Algorithmus der mit relativ hoher Wahrscheinlichkeit das x-te Element einer Liste bzgl. einer Ordnung schneller als in linearer Zeit finden kann.