Die binäre Suche ist ein Algorithmus, der in einer Liste (bzw. einem Array) recht schnell ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente der Liste in einer dem Suchbegriff entsprechenden Weise sortiert sind.

Algorithmus

Zuerst wird das mittlere Element des Arrays oder der Liste ü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 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.

Verschiedene Implementierungen

Pseudocode

Program BinäreSuche

 Eingabe: (S)uchschlüssel, Array (sortiert)

 Variable: SucheErfolgreich = falsch (Boolsche Variable)
 Variable: ErstesElement = 1
 Variable: LetztesElement = Anzahl der Elemente im Array

 Wiederhole 
    Variable: Mitte = (ErstesElement + LetztesElement) DIV 2
    Wenn Mitte = S ist dann 
         SucheErfolgreich = wahr
    Sonst
         Wenn S < als Mitte ist dann 
              links weitersuchen  (LetztesElement = Mitte - 1)
         Sonst  
              rechts weitersuchen (ErstesElement  = Mitte + 1)
         Ende Wenn
    Ende Wenn 
 Solange (SucheErfolgreich = falsch) und (ErstesElement <= LetztesElement)

 Wenn SucheErfolgreich = wahr dann
      Ausgabe: Mitte
 Sonst
     Suche nicht erfolgreich (Suchschlüssel nicht in Array vorhanden)
 Ende Wenn

Ende Programm (BinäreSuche)

Java

class BinäreSuche {

public static void main(String[] args) {

//das Array erzeugen

char[] alphabet = new char[25];

//das Array mit dem Alphabet füllen

for(char c='A', i=0; i<=alphabet.length-1; c++, i++) alphabet[i]=c;

//'D' im Array suchen und auf der Konsole ausgeben

System.out.println("Suchergebniss: "+suche('D', alphabet));

}

/*

* program BinäreSuche

* Eingabe: Suchschlüssel, Array (sortiert)

*/

public static String suche(char s, char[] alphabet) {

String gefundenesElement = null;

//Variable: SucheErfolgreich = falsch (Boolsche Variable)

boolean SucheErfolgreich = false;

//Variable: ErstesElement = 1

int ErstesElement = 0;

//Variable: LetztesElement = Anzahl der Elemente im Array

int LetztesElement = alphabet.length;

int Mitte = 0;

//Wiederhole

do {

//Variable: Mitte = ErstesElement + LetztesElement DIV 2

Mitte = (ErstesElement + LetztesElement) / 2;

/*Wenn Mitte = S dann SucheErfolgreich = wahr */

if (alphabet[Mitte] == s) {

SucheErfolgreich = true;

break;

}

/*Wenn S < als Mitte dann LetztesElement = Mitte - 1 (links weitersuchen)*/

if (s < alphabet[Mitte] ) {

LetztesElement = Mitte - 1;

}

/*Sonst (S > als Mitte) ErstesElemet = Mitte + 1 (rechts weitersuchen)*/

if (s > alphabet[Mitte]){

ErstesElement = Mitte + 1;

}

}

//Solange SucheErfolgreich = falsch und/oder ErstesElement <= LetztesElement

while(SucheErfolgreich = false | ErstesElement <= LetztesElement);

/*Wenn SucheErfolgreich = wahr dann Ausgabe: Mitte */

if (SucheErfolgreich = true) {

gefundenesElement = Character.toString( alphabet[Mitte] );

}

/*sonst Suche nicht erfolgreich (Suchschlüssel nicht in Array vorhanden)*/

else {

System.out.println("Buchstabe nicht in Alphabet vorhanden!");

}

return gefundenesElement;

}

}