6.2 Sequentielle Suche

Bei der sequentiellen (linearen) Suche wird eine Liste Element für Element durchlaufen, bis das gesuchte Element gefunden ist oder das Ende der Liste erreicht wird.

Dieses Verfahren setzt weder eine Sortierung noch eine spezielle Datenstruktur voraus und ist daher universell einsetzbar. Der Algorithmus ist sehr einfach zu implementieren und eignet sich insbesondere für kleine Datenmengen.

Auch große Datenmengen müssen sequentiell durchsucht werden, wenn sie nach einem anderen Kriterium sortiert sind, als es dem Suchkriterium entspricht.

Beispiel: Datensammlung mit 8.000.000 Datensätzen von Personen, die nach Namen sortiert sind. Wenn man jetzt alle Menschen finden will, die am 1. Januar 1991 geboren sind, müsste man den gesamten Datenbestand sequentiell durchsuchen.

6.2.1 Zeitverhalten der sequentiellen Suche

Sei n die Anzahl der Elemente in der Datensammlung (Liste, Array etc.) und S die Suchzeit (in relativen Einheiten).

Günstigster Fall (Best Case)

Das gesuchte Element befindet sich an erster Stelle, daher ist nur ein Vergleich notwendig: S = 1.

Ungünstigster Fall (Worst Case)

Das gesuchte Element steht am Ende der Liste oder kommt gar nicht vor. Daher müssen alle n Elemente geprüft werden: S = n.

Durchschnittlicher Fall (Average Case)

Angenommen, das gesuchte Element befindet sich mit gleicher Wahrscheinlichkeit an jeder Position. Für eine Liste oder Sammlung mit n = 6 ergibt sich dann folgende relative Suchzeit:

S = (1+2+3+4+5+6) / 6 = 21/6 = 3,5

Allgemein erhält man: S = (n+1)/2.

Fazit

Die sequentielle Suche besitzt eine Zeitkomplexität von O(n). Die Laufzeit wächst also linear mit der Anzahl der Elemente.

6.2.2 Implementierung einer sequentiellen Suche

Wir wollen nun eine sequentielle Suche in Java implementieren. Dazu verwenden wir wieder einen int-Array zahlen aus 100 Zufallszahlen.

public int getIndex(int[] zahlen, int suchzahl)
{
   for (int i = 0; i < zahlen.length; i++)
      if (zahlen[i] == suchzahl)
         return i;
   return -1;
}

Diese Methode sucht in dem Array den Index der Suchzahl. Falls die Suchzahl nicht in dem Array vorhanden ist, wird -1 zurückgegeben.