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 und für große Datenmengen, die nach einem anderen Kriterium sortiert sind, wie es bei der Schallplattensammlung oder der großen Datenbank der Fall war.

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.

Im Vergleich zu einfachen Sortierverfahren mit O(n²) erscheint dies zunächst günstig. Allerdings sollte man bedenken, dass bei sehr großen Datenmengen, beispielsweise den 18 Millionen Datensätzen aus dem Datenbank-Beispiel, auch ein lineares Wachstum schnell zu erheblichen Laufzeiten führen kann.

6.2.2 Java-Implementation einer sequentiellen Suche

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

import java.util.Random;

public class ZufallsArraySuche
{
   private int[] zahlen;

   public ZufallsArraySuche()
   {
      zahlen = new int[100];
      fuelleMitZufallszahlen();
   }

   private void fuelleMitZufallszahlen()
   {
      Random rnd = new Random();

      for (int i = 0; i < zahlen.length; i++)
         zahlen[i] = rnd.nextInt(250) + 1;
   }

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

Eigentlich ist die Implementation ganz einfach: Es werden alle Array-Elemente mit der Suchzahl verglichen, und wenn sie gefunden wurde, wird die Methode getIndex() beendet, wobei der Index der gesuchten Zahl zurückgeliefert wird. Falls die Suchzahl nicht im Array enthalten war, wird -1 als Wert zurückgeliefert.

Um diese Klasse zu testen, brauchen wir natürlich auch ein Testprogramm:

import java.util.Random;

public class ZufallsArraySucheTest
{
   public static void main(String[] args)
   {
      ZufallsArraySuche suche = new ZufallsArraySuche();
      Random rnd = new Random();

      for (int i = 1; i <= 20; i++)
      {
         int z = rnd.nextInt(250)+1;
         int index = suche.getIndex(z);

         System.out.printf("Suche nach %3d -> Index: %3d", z, index);
         
         if (index == -1)
            System.out.println("(Zahl nicht im Array!");
         else
            System.out.println();
      }
   }
}

Das Testprogramm erzeugt 20 Zufallszahlen im Wertebereich des Arrays und gibt den Index der gefundenen Zahl oder -1 und "Zahl nicht im Array!" in der Konsole aus.

Hier sehen wir die Konsolenausgabe eines solchen Testlaufs:

Suche nach  53 -> Index:  -1(Zahl nicht im Array!
Suche nach 249 -> Index:  -1(Zahl nicht im Array!
Suche nach 212 -> Index:  -1(Zahl nicht im Array!
Suche nach  39 -> Index:  -1(Zahl nicht im Array!
Suche nach 250 -> Index:  -1(Zahl nicht im Array!
Suche nach  63 -> Index:  64
Suche nach 121 -> Index:  -1(Zahl nicht im Array!
Suche nach 238 -> Index:  -1(Zahl nicht im Array!
Suche nach 205 -> Index:  -1(Zahl nicht im Array!
Suche nach 192 -> Index:  -1(Zahl nicht im Array!
Suche nach  32 -> Index:  -1(Zahl nicht im Array!
Suche nach  89 -> Index:  -1(Zahl nicht im Array!
Suche nach  26 -> Index:  -1(Zahl nicht im Array!
Suche nach  28 -> Index:  66
Suche nach  80 -> Index:  94
Suche nach  29 -> Index:  96
Suche nach 180 -> Index:  -1(Zahl nicht im Array!
Suche nach 128 -> Index:  -1(Zahl nicht im Array!
Suche nach 185 -> Index:  68
Suche nach 138 -> Index:  85

Wie man sieht, werden die meisten erzeugten Suchzahlen nicht gefunden.

Suche in Strings

Dieser Abschnitt wurde nicht in das Skript zur Vorlesung aufgenommen und ist daher auch nicht klausurrelevant! Ich habe den Abschnitt für Interessierte und Wissbegierige geschrieben und weil ich mich selbst dafür interessierte, wie solche Methoden eigentlich implementiert werden.

Die Klasse Strings stellt eine Reihe von Methoden bereit, um Substrings innerhalb eines Strings zu suchen. Eine dieser Methoden ist contains():

public boolean contains(String s)

Ich habe ChatGPT einmal gebeten, mir einen Pseudocode zu erstellen, der verdeutlichen soll, wie diese Methode implementiert ist. Hier das Ergebnis:

for (int i = 0; i <= text.length() - suchstring.length(); i++)
{
    int j = 0;
    while (j < suchstring.length() && text.charAt(i + j) == suchstring.charAt(j))
        j++;

    if (j == suchstring.length())
        return i;  // Treffer
}

return -1; // Kein Treffer

Die äußere for-Schleife beginnt bei i = 0, also am Anfang des zu durchsuchenden Strings. Sie kann jedoch früher enden, nämlich dann, wenn der verbleibende Teil des Strings kürzer ist als der Suchstring.

Beispiel: Der zu durchsuchende String besitzt 100 Zeichen, der Suchstring 12 Zeichen. Dann wird nur bis einschließlich Index 100 - 12 = 88 geprüft. Der restliche Abschnitt ab Index 89 wäre kürzer als das Suchmuster und kann daher keinen Treffer mehr enthalten.

In der inneren while-Schleife wird nun Zeichen für Zeichen geprüft: Zunächst wird das erste Zeichen des Suchstrings mit dem Zeichen an Position i verglichen. Stimmen beide überein, wird das nächste Zeichenpaar geprüft, und der Zähler j wird jeweils inkrementiert. Sobald ein Zeichenpaar nicht übereinstimmt, wird die innere Schleife abgebrochen und die äußere Schleife setzt bei i + 1 fort.

Wenn die while-Schleife beendet wird, weil alle Zeichen des Suchstrings übereingestimmt haben (also j gleich der Länge des Suchstrings ist), wurde ein Treffer gefunden. In diesem Fall gibt der Algorithmus den aktuellen Index i zurück.

Wird die äußere Schleife vollständig durchlaufen, ohne einen Treffer zu finden, liefert der Algorithmus den Wert -1 zurück.

Hier haben wir also ein sehr schönes Beispiel für die sinnvolle Anwendung einer sequentiellen Suche.