Binäres Suchen

Die binäre Suche ist ein Algorithmus, der auf einem Array recht schnell ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente des Array in einer dem Suchbegriff entsprechenden Weise sortiert sind. Der Algorithmus basiert auf dem Schema Teile und Herrsche.

Algorithmus

Zuerst wird das mittlere Element des Arrays ü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 (vorzeitig) beendet.

Jede weiterhin zu untersuchende Hälfte wird wieder gleich behandelt: Das mittlere Element liefert wieder die Entscheidung darüber, wo bzw. ob weitergesucht werden muss.

Die Länge des Suchbereiches wird von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf 1 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.

Komplexität

Um in einem Array mit n Einträgen ein Element zu finden bzw. festzustellen, dass dieses sich nicht im Array befindet, werden maximal log₂n 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 Arrays zu funktionieren. Noch schneller als die binäre Suche ist die Interpolationssuche.

Ähnliche Verfahren

Das hier beschriebene binäre Suchverfahren nennt sich in der Mathematik Intervallschachtelung. Allerdings besteht zwischen diesen beiden Verfahren ein signifikanter Unterschied, da bei der binären Suche nur von der Mitte ausgegangen wird, Intervalle aber an beliebigen Positionen unterteilt werden können.

Verschiedene Implementierungen

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 Array 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 ergebnis = -1;
        int erstes = 0;
        int letztes = alphabet.length - 1;
 
        while (erstes <= letztes && ergebnis < 0) {
            final int mitte = erstes + ((letztes - erstes) / 2);
            if (alphabet[mitte] < zeichen) {
                erstes = mitte + 1; // rechts weitersuchen
            } else if (alphabet[mitte] > zeichen) {
                letztes = mitte - 1; // links weitersuchen
            } else {
                ergebnis = mitte; // Zeichen gefunden
            }
        }
 
        return ergebnis;
    }
 
}

Rekursives Verfahren in Java:

public static int sucheRekursiv(int indexAnfang, int indexEnde, char eingabeZeichen, char[] alphabet) {
 
	// die Mitte zwischen Anfangs- und Endindex festlegen
       	int indexMitte = indexAnfang + ((indexEnde - indexAnfang) / 2);
 
	// wenn das Zeichen mit dem Element des Mitteindexes übereinstimmt
       	if (alphabet[indexMitte] == eingabeZeichen) {
 
            // dann das zurückgeben
            return indexMitte;
 
        } // if 
 
        // wenn Zeichen in der Mitte kleiner ist als Eingabe
       	if (alphabet[indexMitte] < eingabeZeichen) {
 
            // rekursiv die Suche noch mal aufrufen, diesmal aber mit neuem Indexanfang (1. Parameter)
            return sucheRekursiv(indexMitte + 1, indexEnde, eingabeZeichen, alphabet);
 
        } else if (alphabet[indexMitte] > eingabeZeichen) {
 
            // rekursiv die Suche noch mal aufrufen, diesmal aber mit neuem Indexende (2. Parameter)
            return sucheRekursiv(indexAnfang, indexMitte - 1, eingabeZeichen, alphabet);
 
        } else {
 
            // sonst: kein Ergebnis (Zeichen im Alphabet nicht vorhanden)
            return -1;
        }
}

C

Beispiel in C:

/**
 * 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;	
    }
 
 
    while (1) /* 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 rechten Abschnitt weitersuchen */
        else
            links = mitte + 1; /* im linken Abschnitt weitersuchen */
    } 
}

Python

Iteratives Beispiel in Python:

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

Rekursives Verfahren:

 def biSearch(list, key, bottom, top):
    center = (bottom + top)/2
    if list[center] == key:
        return center
    elif top - bottom > 1:
        if list[center] < key:
            return biSearch(list, key, center+1, top)
        else:
            return biSearch(list, key, bottom, center-1)
    else:
        return 'no result'

Weblinks

• Binäre Suche beim Algorithmus der Woche