Infos Home | Impressum | Original Artikel & Autoren Liste

Binäre Suche

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 Elementee der Liste in einer dem Suchbegriff entsprechenden Weise sortiert sind.

Inhalt
1 Algorithmus
2 Komplexität
3 Ähnliche Verfahren
4 Verschiedene Implementierungen

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 log2n 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 auf unsortierten Listen zu funktionieren. Noch schneller als die binäre Suche ist die Interpolationssuche.

Ähnliche Verfahren

Das beschrieben binäre Suchverfahren ähnelt dem Verfahren der Intervallschachtelung.

Verschiedene Implementierungen

Pseudocode

program BinäreSuche

 Sucht den Buchstaben D in einem mit dem Alphabet gefüllten Array

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

Wenn S < als Mitte ist dann
 + links weitersuchen (LetztesElement = Mitte - 1)

Sonst (S>als Mitte)
 + rechts weitersuchen (erstesElemet = Mitte + 1
Solange SucheErfolgreich = falsch und ErstesElement <= LetztesElement

Wenn SucheErfolgreich = wahr dann 

+ Ausgabe: Mitte
sonst 
+ Suche nicht erfolgreich (Suchschlüssel nicht in Array vorhanden)

end 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;
}
}


Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.