Binäre Suche

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.

Verschiedene Implementierungen

Pseudocode

Programm BinäreSuche

 Eingabe: (S)uchschlüssel, (A)rray (sortiert)

 Variable: SucheErfolgreich = falsch (Boolesche Variable)
 Variable: ErstesElement = 1
 Variable: LetztesElement = Anzahl der Elemente im Array
 
 Solange (SucheErfolgreich = falsch) und (ErstesElement <= LetztesElement) mache
    
 Variable: Mitte = ErstesElement + ((LetztesElement - ErstesElement) DIV 2)
    Wenn A[Mitte] = S ist dann 
         SucheErfolgreich = wahr
    Sonst
         Wenn S < als A[Mitte] ist dann 
              links weitersuchen  (LetztesElement = Mitte - 1)
         Sonst  
              rechts weitersuchen (ErstesElement  = Mitte + 1)
         Ende Wenn
    Ende Wenn 
 
 Ende Solange 
 
 Wenn SucheErfolgreich = wahr dann
     Ausgabe: A[Mitte]
 Sonst
     Ausgabe: Suche nicht erfolgreich (Suchschlüssel nicht in Array vorhanden)
 Ende Wenn

Ende Programm (BinäreSuche)

Java

Das folgende Beispiel definiert eine Klasse de.wikipedia.org.BinäreSuche 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 der gegebene Array sortiert sein.

package de.wikipedia.org;

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) {
            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;
    }

}

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      Groesse 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 links = 0;
    unsigned int mitte;
    unsigned int rechts = n - 1;
	
    if (M == NULL || n <= 0 || X < M[0] || X > M[n - 1]) //Bereichsüberprüfung
    {
        return 0;	
    }
	
    while (links <= rechts)
    {
        mitte = links + ((rechts - links) / 2);

        if (M[mitte] == X) // Element X gefunden?
        {
            *index = mitte;
            return 1;
        }

        if (M[mitte] > X)
            rechts = mitte - 1;        
        else
            links = mitte + 1;
    }
    
    return 0; // X nicht in M!
}

Siehe auch

Suchverfahren