- Sequenzielle Suche
-
Lineare Suche ist ein Algorithmus, der auch unter dem Namen sequenzielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt.
Die Aufgabe besteht darin, ein Element in einer Liste oder einem Array mit n Elementen zu finden. Man geht dazu die Liste Element für Element durch, bis man es gefunden hat. Der Suchaufwand wächst linear mit der Anzahl der 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.
Wenn die Anzahl der Elemente in einer Liste klein ist, dann ist es oft auch das effizienteste Verfahren.
Die effizientere Binäre Suche kann nur bei geordneten 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.
Inhaltsverzeichnis
Implementierung in Pseudocode
BEGINN LinearSearch EINGABE: (S)uchschlüssel, (A)rray VARIABLE: N = Anzahl Elemente im Array 'A' VARIABLE: SucheErfolgreich = falsch VARIABLE: i = 0 FÜR i BIS N ODER SucheErfolgreich WENN A[i] = S DANN SucheErfolgreich = wahr WENN SucheErfolgreich = wahr DANN AUSGABE: i SONST AUSGABE: Suche nicht erfolgreich ENDE
Beispielimplementierung in Ruby
def Lineare_suche(datenArray,wert) for i in datenArray return true if i == wert; end return false end
Beispielimplementierung in Objective CAML
let rec linsuche = function ([],a) -> false | (x::t,a) -> if x = a then true else linsuche(t,a);;
Beispielimplementierung in Java
Das Beispiel gibt den Wert
-1
zurück, wenn das gesuchte Element nicht im Array „daten
“ vorhanden ist. Ansonsten gibt es die Position des Elementes zurück.public static int lineareSuche(final int gesucht, final int daten[]) { int result = -1; for (int i = 0; result < 0 && i < daten.length; i++) { if (daten[i] == gesucht) { result = i; } } return result; }
Beispielimplementierung in Python
Findet alle Suchschlüssel in der Liste.
def lineare_suche(liste): maxindex = len(liste) suche_erfolgreich = False eingabe = input("Geben Sie die zu suchende Zahl ein: ") for index in xrange(0, maxindex): print index if liste[index] == eingabe: suche_erfolgreich = True print "Die gesuchte Zahl", eingabe, "befindet sich auf dem Platz mit dem Index ", index if not suche_erfolgreich: print "Die Suche war nicht erfolgreich"
Findet den ersten Suchschlüssel in der Liste.
def linearSearch(list, key): success=False index=0 while index < len(list) and not success: if list[index] == key: success=True return index index+=1 return 'Kein Element gefunden'
Siehe auch
Wikimedia Foundation.