Sequenzielle Suche

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.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • sequenzielle Suche — sequenzielle Suche,   Suchalgorithmen …   Universal-Lexikon

  • Sequentielle 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… …   Deutsch Wikipedia

  • lineare Suche —   (sequenzielle Suche), die einfachste aller Suchmethoden in Datenbanken. Hierbei wird der Reihe nach jeder Datensatz mit dem Suchbegriff verglichen, so lange, bis ein Datensatz mit den gesuchten Merkmalen gefunden oder die Liste der Datensätze… …   Universal-Lexikon

  • Suchalgorithmen — Suchalgorithmen,   Verfahren (Algorithmen), in einem vorgegebenen Datenbestand ein oder alle Objekte zu ermitteln, die eine bestimmte Bedingung, das Suchkriterium, erfüllen. Folgende Suchalgorithmen sind gebräuchlich:   sequenzielle Suche:… …   Universal-Lexikon

  • Arzneimittelforschung — Als Pharmaforschung wird die in Pharmaunternehmen und Universitäten betriebene gezielte Suche nach neuen Wirkstoffen, neuen Wirkstoffkombinationen, neuen galenischen Formen, neuen Anwendungsgebieten für bestehende Arzneimittel und die Entwicklung …   Deutsch Wikipedia

  • Klinische Entwicklung — Als Pharmaforschung wird die in Pharmaunternehmen und Universitäten betriebene gezielte Suche nach neuen Wirkstoffen, neuen Wirkstoffkombinationen, neuen galenischen Formen, neuen Anwendungsgebieten für bestehende Arzneimittel und die Entwicklung …   Deutsch Wikipedia

  • Pharmaforschung — Als Pharmaforschung wird die in Pharmaunternehmen und Universitäten betriebene gezielte Suche nach neuen Wirkstoffen, neuen Wirkstoffkombinationen, neuen galenischen Formen, neuen Anwendungsgebieten für bestehende Arzneimittel und die Entwicklung …   Deutsch Wikipedia

  • Informationsökonomik — von Professor Dr. Dr.h.c.mult. Arnold Picot und Professor Dr. Birgitta Wolff I. Gegenstand und Bedeutung Gegenstand der Informationsökonomik ist die Analyse ökonomischer Systeme unter besonderer Berücksichtigung der Tatsache, dass die… …   Lexikon der Economics

  • Nephronblockade — Die sequenzielle Nephronblockade ist ein seit ca. 1985 bekanntes pharmakologisches Konzept bei der Behandlung von akuten Ödemen mit Diuretika (harntreibenden Mitteln). Die übliche Monotherapie mit einem einzelnen Schleifendiuretikum ist… …   Deutsch Wikipedia

  • Kreativitätstechniken — Ideenfindungsmethoden. 1. Charakterisierung: Suchregeln oder Heuristiken (⇡ Heuristik), die individuelle Gedankengänge oder gruppenorientierte Suchprozesse stimulieren (Stimulation eines kreativen Prozesses), bes. bei Problemstellungen, die… …   Lexikon der Economics

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”