Binäre Suche
aus Wikipedia, der freien Enzyklopädie
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.
Inhaltsverzeichnis |
[Bearbeiten] 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.
[Bearbeiten] 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 in unsortierten Arrays zu funktionieren. Noch schneller als die binäre Suche ist die Interpolationssuche.
[Bearbeiten] Ä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.
[Bearbeiten] Verschiedene Implementierungen
[Bearbeiten] 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)
[Bearbeiten] Java
Das folgende 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 der 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 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) { 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; } }
[Bearbeiten] 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 = 1;
unsigned int rechts = n - 1;
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);
if (rechts < links) // Falls dies wahr liefert, weiss man, dass X nicht in M ist
{
printf("Nicht gefunden!\n");
return 0;
}
else if (M[mitte] == X) // Element X gefunden?
{
*index = mitte;
return 1;
}
if (M[mitte] > X)
rechts = mitte - 1;
else
links = mitte + 1;
}
}
[Bearbeiten] Python
Iteratives Verfahren
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'
