Binäre Suche

Die binäre Suche ist ein Algorithmus, der auf einem Feld sehr effizient ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente in dem Feld entsprechend einer totalen Ordnungsrelation angeordnet („sortiert“) sind. Der Algorithmus basiert auf einer einfachen Form des Schemas Teile und Herrsche.

Algorithmus

Zuerst wird das mittlere Element des Felds überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche beendet.

In der zu untersuchenden Hälfte (und erneut in den folgenden Hälften) wird genauso verfahren: Das mittlere Element liefert wieder die Entscheidung darüber, ob und wo weitergesucht werden muss. Die Länge des Suchbereiches wird so von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf ein einzelnes Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.

Der Algorithmus zur binären Suche wird entweder als Iteration oder Rekursion implementiert. Um ihn verwenden zu können, müssen die Daten bereits sortiert und in einer Datenstruktur vorliegen, in der gezielt auf das n-te Element zugegriffen werden kann. Auf einer einfachen verketteten Liste ist dies also nicht möglich (siehe aber Skip-Liste).

Fallstrick

Wenn bei den Indizes an der Kapazitätsgrenze des Wortes gearbeitet wird, muss bei der Mittebildung ein Additions-Überlauf des Wortes vor der Division durch 2 vermieden werden. Dies kann fast nur dann Probleme machen, wenn bei den Indizes mit einem kürzeren Wort gearbeitet wird, als es ein Zeiger ist. Denn wenn mit der gleichen Wortgröße für Index und Zeiger gearbeitet wird und wenn vorzeichenlose Indizes verwendet werden, dann müsste ein Eintrag im Feld eine Länge von weniger als 2 haben und das Feld fast den ganzen Adressraum ausfüllen, damit Probleme auftauchen können.

Die defensive Art der Programmierung mit Mittebildung über die Differenzbildung ist in den Beispielen gelegentlich aufgezeigt.

Komplexität

Um in einem Feld mit $n$ Einträgen ein Element zu finden bzw. festzustellen, dass dieses sich nicht im Feld befindet, werden maximal $\lceil \log_2 n \rceil$ Schritte benötigt. Somit liegt die binäre Suche, in der Landau-Notation ausgedrückt, in der Komplexitätsklasse $O(\log\ n)$. Damit ist sie deutlich schneller als die lineare Suche, welche allerdings den Vorteil hat, auch in unsortierten Feldern zu funktionieren. In Spezialfällen kann die Interpolationssuche schneller sein als die binäre Suche.

Ähnliche Verfahren und Varianten

Intervallschachtelung

→ Hauptartikel: Intervallschachtelung

Das hier beschriebene binäre Suchverfahren kann als eine (endliche) Ausprägung der Intervallschachtelung aus der mathematischen Analysis angesehen werden.

Binärer Suchbaum

→ Hauptartikel: Binärer Suchbaum

Der Such-Algorithmus entspricht auch der Suche in einem binären Suchbaum, wenn man das Array als solchen interpretiert: das mittlere Element ist die Wurzel, die Mitten der so entstehenden Hälften die Wurzeln der entsprechenden Teilbäume und so fort. Der aus dieser Interpretation resultierende Binärbaum ist sogar balanciert. Teilt man nicht in der Mitte, so ist das Ergebnis immer noch ein binärer Suchbaum, jedoch ist er u. U. nicht mehr balanciert.

Die große Überlegenheit des binären Suchbaums gegenüber der binären Suche im Array liegt erstens im besseren Verhalten bei Einfügungen und Löschungen, bei denen im Mittel ein linearer Aufwand anfällt. Bei Bäumen gibt es auch in diesen Fällen Implementierungen mit garantiert logarithmischer Laufzeit. Dort ist auch die Speicherverwaltung einfacher, da Änderungen nicht das ganze Array betreffen, sondern sich mit dem Entstehen oder Verschwinden eines Elementes direkt verbinden lassen. Zweitens können Bäume besser als das Array an Häufigkeiten angepasst werden. Wenn aber das Array schon fertig sortiert ist und sich dann nicht mehr ändert und Zugriffswahrscheinlichkeiten keine Rolle spielen sollen, ist das Array ein gutes Verfahren.

Binäre Suche und totale Quasiordnung

Da das Array als endlicher Definitionsbereich einer Funktion angesehen werden kann, die natürlich nicht notwendigerweise injektiv sein muss, lässt sich das Vorkommen von Duplikaten leicht über die Funktionswerte regeln. Und wenn die Ordnungsrelation von vorn herein schon keine Totalordnung, sondern nur eine totale Quasiordnung ist, ist es ggf. sparsamer, die Äquivalenzklassen vor dem Vergleichen zu bilden, als alle möglichen Duplikate im Array zu halten.

Beispiel

In einer Sammlung von Schlüsselwörtern soll zwar Groß- und Kleinschreibung zulässig sein, die Schlüsselwörter sollen sich aber in ihrer Bedeutung nicht unterscheiden.

Interpolationssuche

→ Hauptartikel: Interpolationssuche

Bei der Interpolationssuche wird das Array nicht mittig geteilt, sondern per linearer Interpolation die Position des gesuchten Elementes abgeschätzt. Sind die Schlüssel in etwa äquidistant verteilt, so kann das gesuchte Element in nahezu konstanter Zeit gefunden werden. In einem ungünstigen Fall wird die Laufzeit jedoch linear. Abgesehen davon muss der Definitionsbereich sich für eine lineare Interpolation eignen.

Quadratische Binärsuche

→ Hauptartikel: Quadratische Binärsuche

Bei der quadratischen Binärsuche versucht man die Vorteile der Interpolationssuche mit denen der normalen Binärsuche zu kombinieren und mittels Interpolation in jeder Iteration den Suchraum auf ein Intervall der Länge $\sqrt n$ zu verkleinern.

Verschiedene Implementierungen

In zahlreichen Programmiersprachen ist diese Algorithmus in den Klassenbibliotheken verfügbar. In Java beispielsweise als java.util.Arrays.binarySearch und java.util.Collections.binarySearch, in Python als das Paket bisect und in C++/STL als std::binary_search im "algorithms" header.

Pseudocode

Beispiel in Pseudocode:

 Programm BinäreSuche
 
     Eingabe: (S)uchschlüssel, (A)rray (sortiert)
     Ausgabe: Position, an der sich der Suchschlüssel befindet, bzw. 0, falls er nicht vorkommt
 
     Variable: SucheErfolgreich = falsch (Boolesche Variable)
     Variable: Anfang = 1
     Variable: Ende = Anzahl der Elemente im Array
 
     Solange (SucheErfolgreich = falsch) und (Anfang ≤ Ende) mache
         Variable: Mitte = (Anfang + Ende) DIV 2
         Wenn A[Mitte] = S ist dann
             SucheErfolgreich = wahr
         Sonst
             Wenn S < als A[Mitte] ist dann
                 links weitersuchen: Ende = Mitte - 1
             Sonst
                 rechts weitersuchen: Anfang = Mitte + 1
             Ende Wenn
         Ende Wenn
     Ende Solange
 
     Wenn SucheErfolgreich = wahr dann
         Ausgabe: Mitte
     Sonst
         Ausgabe: 0 (Suchschlüssel nicht in Feld vorhanden)
     Ende Wenn
 
 Ende Programm (BinäreSuche)

Java

Das folgende, iterative Java-Beispiel definiert eine Klasse mit einer Methode suche, die als Parameter ein gesuchtes Zeichen und ein zu durchsuchendes Alphabet in Form eines Arrays erwartet.

Die Methode gibt den Index des Zeichens zurück, falls es im Alphabet enthalten ist, anderenfalls −1. Damit die Methode funktioniert, muss das gegebene Array sortiert sein. Enthält das Array mehrere Elemente des gesuchten Zeichens, so ist in dieser Implementierung nicht bestimmt welches Zeichen gefunden wird.

package org.wikipedia.de;
 
public final class BinäreSuche {
 
    public static int suche(final char zeichen, final char[] alphabet) {
        int erstes = 0;
        int letztes = alphabet.length - 1;
 
        while (erstes <= letztes) {
            final int mitte = erstes + ((letztes - erstes) / 2); // vermeidet Überläufe des int
            if (alphabet[mitte] < zeichen) {
                erstes = mitte + 1; // rechts weitersuchen
            } else if (alphabet[mitte] > zeichen) {
                letztes = mitte - 1; // links weitersuchen
            } else {
                return mitte; // Zeichen gefunden
            }
        }
 
        return -1;
    }
 
}

Rekursives Verfahren in Java:

public static int sucheRekursiv(int indexAnfang, int indexEnde, char eingabeZeichen, char[] alphabet) {
    if(indexAnfang > indexEnde) {
        return -1;
    }
 
    int indexMitte = indexAnfang + ((indexEnde - indexAnfang)/2);
 
    if(eingabeZeichen > alphabet[indexMitte]) {
        return sucheRekursiv(indexMitte + 1, indexEnde, eingabeZeichen, alphabet);
    }
 
    if(eingabeZeichen < alphabet[indexMitte]) {
        return sucheRekursiv(indexAnfang, indexMitte - 1, eingabeZeichen, alphabet);
    }
 
    return indexMitte;
}

C

Beispiel in C (iterativ):

/**
 * Liefert 1 zurück, wenn X in M gefunden wurde, ansonsten 0.
 * Beim Aufruf wird als 4. Argument eine Variable per Adresse
 * übergeben, in die bei Erfolg die Position von X in M geschrieben wird.
 * @param const int[] M      Feld, in dem gesucht werden soll
 * @param int n              Größe des Feldes
 * @param int X              der gesuchte Eintrag
 * @param int *index         Position des gesuchten Eintrags X in M
 * @return int 1=gefunden, 0=nicht gefunden
 */
int binary_search(const int M[], int n, int X, int *index)
{
    unsigned int mitte;
    unsigned int links = 0; /* man beginne beim kleinsten Index */
    unsigned int rechts = n - 1; /* Arrays sind 0-basiert */
 
    if (M == NULL || n <= 0 || X < M[0] || X > M[n - 1]) /* Bereichsüberprüfung */
    {
        return 0;
    }
 
 
    for (;;) /* Die endlose Schleife wird durch returns unterbrochen */
    {
        mitte = links + ((rechts - links) / 2); /* Bereich halbieren */
 
        if (rechts < links) /* alles wurde durchsucht, aber X nicht gefunden */
        {
             printf("Nicht gefunden!\n");
             return 0;
        }
 
        if (M[mitte] == X) /* Element X gefunden? */
        {
            *index = mitte;
            return 1;
        }
 
        if (M[mitte] > X)
            rechts = mitte - 1; /* im linken Abschnitt weitersuchen */
        else
            links = mitte + 1; /* im rechten Abschnitt weitersuchen */
    }
}

Python

Iteratives Beispiel in Python:

 def binaere_suche(liste):
    maxindex = len(liste) - 1
    index = 0
    eingabe = int(raw_input("Geben Sie die zu suchende Zahl ein: "))
    while index <= maxindex:
        mitte = index + ((maxindex - index)/2)
        if liste[mitte] == eingabe:
            print "Die gesuchte Zahl", eingabe, "befindet sich auf dem Index", mitte
            return
        elif eingabe < liste[mitte]:
            maxindex = mitte - 1
        else:
            index = mitte + 1
    print "Die Suche war nicht erfolgreich"

Rekursives Verfahren:

 def binaersuche_rekursiv(werte, gesucht, start, ende):
    if ende < start:
        return 'nicht gefunden'
    mitte = (start + ende)/2
    if werte[mitte] == gesucht:
        return mitte
    elif werte[mitte] < gesucht:
        return binaersuche_rekursiv(werte, gesucht, mitte+1, ende)
    else:
        return binaersuche_rekursiv(werte, gesucht, start, mitte-1)

Ada

Beispiel in Ada (iterativ):

procedure binaere_Suche (
      A : in Array Type;
      E : in Integer ;
      P : out Integer) is
  L,
  M,
  R : Integer ;
  W : Boolean := True;
begin
  L := A'First;
  R := A'Last;
  while L <= R and W loop
      M := (R + L) / 2;
      if A (M) = E then
         P := M;
         W := False;
      elsif A (M) > E then
         R := M − 1;
      else
         L := M + 1;
      end if;
  end loop;
   if W then
      P := −1;
  end if;
end binaere_Suche;

Haskell

Beispiel in der funktionalen Programmiersprache Haskell (rekursiv):

 binSearch :: Ord a => a -> [a] -> Bool
 binSearch b [] = False
 binSearch b x
  | (b==mid) = True
  | (b<mid) = binSearch b left
  | (b>mid) = binSearch b right
   where
     half = (length x) `div` 2
     left = take half x
     right = drop half x
     mid = head right

Weblinks

• Binäre Suche beim Algorithmus der Woche