6.1 Lineare Suche

Allgemeines zum Suchen

Suchen gehört zu den häufigsten Aufgaben, die Computer im Alltag übernehmen – ob beim Auffinden von Internetadressen, Telefonnummern, Artikeln oder Dateien. Suchalgorithmen spielen daher eine zentrale Rolle in der Informatik.

Grundsätzlich unterscheidet man beim Suchen nach dem Zustand der Daten, die durchsucht werden sollen. Es ergeben sich dabei drei typische Situationen:

• Die Daten sind unsortiert.
• Die Daten sind einfach sortiert (z. B. alphabetisch oder numerisch aufsteigend).
• Die Daten sind suchfreundlich strukturiert, z. B. in einem binären Suchbaum.

Sind die Daten nicht sortiert, bleibt nur die lineare Suche (auch sequentielle Suche genannt). Dabei werden die Elemente nacheinander durchsucht – beginnend beim ersten Eintrag, bis entweder das gesuchte Element gefunden oder das Ende der Daten erreicht ist.

Sind die zu durchsuchenden Daten aber sortiert, kann man viel bessere Suchverfahren einsetzen.

Dieses Beispiel sollte zeigen, wie sinnvoll es ist, Daten nach bestimmten Kriterien zu sortieren. Darum haben wir in der letzten Folge ja auch die verschiedenen Sortierverfahren ausführlich besprochen.

Manchmal hilft auch das Sortieren nichts

Noch mal zurück zum Beispiel mit dem Bücherregal. Wenn die Bücher nach Erscheinungsdatum sortiert sind, Sie aber einen bestimmten Autoren suchen, hilft die ganze Sortiererei nichts. Es müsste erst jemand die ganzen Bücher neu sortieren, nämlich nach Autor(in). Und dann kommt der nächste Kunde und sucht Bücher, die in der letzten Woche neu herausgekommen sind - Pech gehabt.

Auch die Suche in einer Datenbank kann durchaus sequentiell verlaufen, nämlich dann, wenn zwar Index-Dateien für bestimmte Keys (Schlüsselwerte) existieren, wenn Sie aber nach einer Kombination von zwei oder drei Schlüsselwerten suchen.

Fallbeispiel

Lineare Suche

Bei der linearen oder sequentiellen Suche wird jedes Element einer ungeordneten Liste nacheinander überprüft, bis entweder das gesuchte Element gefunden wurde oder alle Einträge durchsucht sind. Dieses Verfahren ist universell einsetzbar, da keinerlei Sortierung oder besondere Datenstruktur vorausgesetzt wird. Der Algorithmus ist daher sehr einfach zu implementieren und eignet sich besonders für kleine Datenmengen - oder ist notwendig für große Datenmengen, die nach einem anderen Kriterium sortiert sind (siehe obiges Fallbeispiel).

Zeitverhalten

Günstigster Fall (best case)

Im günstigsten Fall befindet sich das gesuchte Element direkt am Anfang des Arrays, die Suchzeit wäre hier also S = 1.

Ungünstigster Fall (worst case)

In diesem Fall befindet sich das gesuchte Element ganz am Ende des Arrays oder kommt in dem Array nicht vor. Wenn das der Fall ist, müssen alle n Element des Arrays untersucht werden, die Suchzeit würde hier also S = n betragen.

Durchschnittlicher Fall (average case)

Wir wollen einmal die durchschnittliche Suchzeit für ein Array aus n=6 Elementen berechnen. Falls es sich bei dem gesuchten Wert um das erste Element handelt, ist S = 1 (S = Suchzeit). Findet man das Gesuchte erst an zweiter Stelle, ist S = 2 und so weiter. Wenn erst das letzte Element mit dem gesuchten übereinstimmt, ist S = 6. Also berechnet sich die durchschnittliche Suchzeit mit

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

Das entspricht genau (n+1) /2 und entspricht auch dem, was man in den meisten Fachbüchern findet, zum Beispiel in [1].

Somit kann man also sagen, dass die sequentielle bzw. lineare Suche eine Zeitkomplexität von O(N) hat. Das hört sich eigentlich gar nicht mal so schlecht an, wenn man bedenkt, dass die einfachen Sortierverfahren eine Zeitkomplexität von O(N²) haben.

Java-Methoden

Gegeben ist ein unsortierter Array aus int-Zahlen. Eine Methode zum Suchen eines Elementes könnte so aussehen:

public int getPos(int[] array, int suchzahl)
{
   for (int pos=0; pos < array.length; pos++)
   {
      if (suchzahl == array[pos])
         return pos;
   }
   return -1;
}

Diese Methode beginnt mit der Suche nach der Suchzahl von vorn, d.h., zunächst wird das erste Arrayelement geprüft, dann das zweite und so weiter. Wenn das Arrayelement gefunden wurde, das mit der Suchzahl übereinstimmt, wird der Index dieses Elementes zurückgeliefert.

Eine contains() oder enthaelt()-Methode kann man nun leicht implementieren:

public boolean contains(int[] array, int suchzahl)
{
   return getPos(array,suchzahl) != 1;
}

Suche in Strings

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.