Skip to Content

Sequentielle Suche (lineare Suche)

 Die sequentielle Suche beruht auf dem naiven Ansatz einen Datenbestand vollständig zu durchsuchen bis das passende Element gefunden wird. Dieses Verfahren nennt man auch erschöpfende Suche oder im englischen das Greedy-Schema (engl. für gefräßig). Der Algorithmus für das Durchsuchen eines Felds ist der folgende:

  1. Spezifiziere Suchschlüssel
  2. Vergleiche jedes Element mit dem Suchschlüssel
    1. Erfolgsfall: Liefere Indexposition beim ersten Auffinden des Objekts und beende das Suchen
    2. Kein Erfolg: Gehe zum nächsten Objekt und vergleiche es.
  3. Gib eine Meldung über das erfolglose Suchen zurück wenn das Ende des Datenbestands erreicht wurde ohne das, das Objekt gefunden wird. Dies kann eine java-Ausnahme sein oder ein spezieller Rückgabewert (z.Bsp .1)

Der Aufwand für diesen Algorithmus ist linear, also O(n). Die Anzahl der nötigen Vergleichsoperationen hängt direkt von der Anzahl der Elemente im Datenbestand ab. Im statischen Mittel sind dies n/2 Vergleiche.

Sequentielle Suche in einem unsortierten Datenbestand

In diesem Fall muss bei jeder Suche der gesamte Datenbestand durchlaufen werden bis ein Element gefunden wurde

Beispiel einer Javaimplementierung

Die Methode sequentielleSuche() durchsucht ein Feld von 32 Bit Ganzzahlen nach einem vorgegebenen Schlüssel schluessel und gibt den Wert -1 zurück wenn kein Ergebnis gefunden wird.

public static int sequentielleSuche() (int[] feld, int schluessel) {
   int suchIndex = 0;
      while (suchIndex< feld.length && feld[suchIndex] != schluessel) suchIndex++;
      if (suchIndex == feld.length) suchindex = -1; // Nichts gefunden
   return suchindex;
}

Sequentielle Suche in einem sortierten Datenbestand

Bei einem sortierten Datenbestand kann man die Suche optimieren in dem man sie abbricht so bald man weiß, das die folgenden Elemente alle größer bzw. kleiner als das gesucht Element sind. Man muss also nicht das Feld vollständig durchlaufen. Hierdurch lässt sich Zeit sparen. Der durchschnittliche Aufwand von n/2 bleibt jedoch ein linearer Aufwand.

Beispiel einer Javaimplementierung

Die Methode sequentielleSuche() durchsucht ein Feld von 32 Bit Ganzzahlen nach einem vorgegebenen Schlüssel schluessel und gibt den Wert  -1 zurück wenn kein Ergebnis gefunden wird.

public static int sequentielleSuche() (int[] feld, int schluessel)
   int suchIndex = 0;
   while (suchIndex< feld.length && feld[suchIndex] < schluessel) suchIndex++;
      if ((suchindex < feld.length) && (feld[suchIndex] == feld[schluessel])) 
           return suchindex; // Erfolg
      else return -1; //kein Erfolg
}

Comments

typo

"3. Gib eine Meldung über das erfolglose Suchen zurück wenn das Ende des Datenbestands erreicht wurde ohne dass das Objekt gefunden wird. Dies kann eine java-Ausnahme sein oder ein spezieller Rückgabewert (z.Bsp .1)"

Gut erkannt!

Gut erkannt!



book | by Dr. Radut