Binäre Suche

Grundidee und Voraussetzungen

Die binäre Suche ist ein Algorithmus, der in einem Array ein gesuchtes Element sehr effizient findet oder zuverlässig feststellt, dass es nicht vorhanden ist. Sie folgt dem Prinzip „Teile und Herrsche“ und ist zugleich ein Greedy-Algorithmus: In jedem Schritt wird anhand eines Vergleichs entschieden, welche Hälfte des verbleibenden Suchbereichs noch infrage kommt.

Voraussetzung ist, dass die Werte entsprechend einer totalen Ordnungsrelation sortiert sind und dass direkt auf das n-te Element zugegriffen werden kann. Auf einer einfachen verketteten Liste geht deshalb der Effizienzvorteil verloren. Die Sortierung und die Suche müssen denselben Schlüssel verwenden. In einem nach Namen sortierten Telefonbuch kann beispielsweise binär nach einem Namen, aber nicht nach einer Telefonnummer gesucht werden.

Gleiche Werte dürfen mehrfach vorkommen. Wird ein mehrfach vorhandener Suchwert gefunden, ist grundsätzlich nicht festgelegt, welche seiner Positionen ausgegeben wird. Bei einer erfolglosen Suche kann zusätzlich die Position bestimmt werden, an der der Wert eingefügt werden müsste, damit das Array sortiert bleibt.

Ablauf des Algorithmus

Zu Beginn umfasst der Suchbereich das vollständige Array. Dann wird wiederholt folgender Ablauf ausgeführt:

• Ist der Suchbereich leer, kommt der Suchwert nicht vor.
• Die Mitte des aktuellen Suchbereichs wird berechnet und der dort gespeicherte Wert mit dem Suchwert verglichen.
• Sind beide Werte gleich, ist die Suche erfolgreich; die Position der Mitte wird ausgegeben.
• Ist der Suchwert kleiner, wird nur in der linken Hälfte weitergesucht. Der rechte Rand wird auf die Position unmittelbar links von der Mitte gesetzt.
• Ist der Suchwert größer, wird nur in der rechten Hälfte weitergesucht. Der linke Rand wird auf die Position unmittelbar rechts von der Mitte gesetzt.

Der Suchbereich wird somit in jedem Schritt ungefähr halbiert. Spätestens bei einem Bereich mit nur einem Element entscheidet sich, ob dieses Element gesucht war. Ist es das nicht, steht zugleich fest, an welcher Stelle der Suchwert einsortiert werden müsste.

Der Algorithmus kann iterativ, also mit einer Schleife, oder rekursiv, also durch wiederholte Selbstaufrufe einer Funktion, umgesetzt werden.

Beispiel und Effizienz

In einer alphabetisch sortierten Liste mit 13 Buchstaben wird nach G gesucht. Zuerst wird die mittlere Position mit ganzzahliger Division bestimmt: 13 \ 2 = 6. An Position 6 steht J. Weil G im Alphabet vor J liegt, kann G nur vor dieser Position vorkommen.

Im verbleibenden linken Bereich wird erneut die Mitte geprüft: 6 \ 2 = 3. Dort steht F. Weil G größer als F ist, bleibt nur der Bereich zwischen F und J. Dessen Mitte liegt an Position (Position(F) + Position(J)) \ 2 = 4; dort befindet sich G. Damit waren nur drei Vergleiche nötig. Selbst im schlechtesten Fall wären bei den 13 Elementen nur vier Vergleiche erforderlich gewesen.

Bei der Suche nach I würde nach den Vergleichen mit J, F und G noch der Bereich zwischen G und J untersucht. Dort steht H, das kleiner als I ist. Zwischen H und J bleibt kein Element übrig. I ist daher nicht enthalten und müsste hinter Position 5 eingefügt werden.

Eine lineare Suche würde die Liste dagegen von vorn nach hinten durchlaufen und im ungünstigsten Fall alle 13 Elemente prüfen, etwa wenn Z am Ende stünde oder nicht vorhanden wäre. Der Vorteil der binären Suche wächst daher mit der Größe des Arrays.

Komplexität und verwandte Verfahren

Für ein Array mit n Einträgen benötigt die binäre Suche höchstens ⌈log₂(n+1)⌉ = ⌊log₂(n)+1⌋ Vergleiche. Ihre Zeitkomplexität beträgt in der Landau-Notation O(log n). Sie ist damit deutlich schneller als die lineare Suche, die allerdings auch auf unsortierten Arrays funktioniert.

Das Verfahren kann als endliche Form der Intervallschachtelung aus der mathematischen Analysis verstanden werden. Es entspricht außerdem der Suche in einem vollständig balancierten binären Suchbaum: Das mittlere Arrayelement bildet die Wurzel, die Mitten der beiden Hälften bilden die Wurzeln der Teilbäume. Die Pfadlängen von den Blättern zur Wurzel unterscheiden sich dabei um höchstens 1. Für n Elemente ist dieser Baum hinsichtlich der maximalen Pfadlänge h := ⌈log₂(n+1)⌉, der Pfadlängensumme 1+(n+1)h−2^h und der mittleren Pfadlänge optimal. Letztere entspricht bei gleich wahrscheinlichen Elementen der mittleren Vergleichszahl. Eine Teilung außerhalb der Mitte erzeugt weiterhin einen binären Suchbaum, aber möglicherweise keinen balancierten und optimalen.

Binäre Suchbäume sind besonders bei Einfügungen und Löschungen vorteilhaft. Bei Arrays entsteht dafür im Mittel linearer Aufwand, während Baumimplementierungen garantierte logarithmische Laufzeit ermöglichen können. Bäume lassen sich außerdem besser an unterschiedliche Zugriffshäufigkeiten anpassen. Ein bereits sortiertes, unveränderliches Array bleibt dagegen gut geeignet, wenn Zugriffswahrscheinlichkeiten keine Rolle spielen.

Bei einer totalen Quasiordnung können verschiedene Werte als gleichwertig gelten. Dann kann es sparsamer sein, vor dem Vergleichen Äquivalenzklassen zu bilden, statt alle Duplikate zu speichern. Ein Beispiel sind Schlüsselwörter, bei denen Groß- und Kleinschreibung erlaubt ist, aber keinen Bedeutungsunterschied erzeugt.

Die Interpolationssuche teilt das Array nicht in der Mitte, sondern schätzt die Position durch lineare Interpolation. Bei ungefähr äquidistant verteilten Schlüsseln kann sie nahezu konstante Zeit erreichen; im ungünstigen Fall ist ihre Laufzeit jedoch linear. Außerdem muss sich der Definitionsbereich für lineare Interpolation eignen. Die quadratische Binärsuche verbindet beide Ansätze und versucht, den Suchraum durch Interpolation in jeder Iteration auf ein Intervall der Länge √n zu verkleinern.

Praktische Implementierung

Viele Programmiersprachen stellen die binäre Suche bereits bereit, etwa Java mit java.util.Arrays.binarySearch, Python mit dem Paket bisect und C++/STL mit std::binary_search. Üblicherweise wird bei Erfolg die gefundene Arrayposition zurückgegeben. Bei Misserfolg liefern Implementierungen häufig die Position, an der der Eintrag stehen müsste, von −1 ausgehend rückwärts gezählt.

Bei großen Arrays darf die Mitte nicht unvorsichtig als (links + rechts) ÷ 2 berechnet werden, weil die Addition einen Überlauf verursachen kann. Sicherer ist links + (rechts − links) ÷ 2.

Gelten der linke und der rechte Rand als eingeschlossen, muss außerdem ein möglicher Unterlauf beachtet werden: Ist die Mitte 0 und soll der rechte Rand auf die vorherige Position gesetzt werden, ergibt sich ein negativer Wert. Bei einem vorzeichenlosen Datentyp würde dieser unterlaufen und könnte dazu führen, dass die Schleifenbedingung dauerhaft erfüllt bleibt, also eine Endlosschleife entsteht.

Eine iterative Python-Variante setzt links zunächst auf 0 und rechts auf len(folge)−1. Solange links ≤ rechts gilt, berechnet sie mitte = links + (rechts−links) // 2. Bei Gleichheit liefert sie „Position“ und den Index. Ist der mittlere Wert größer als der Suchwert, wird rechts = mitte−1 gesetzt; andernfalls links = mitte+1. Endet die Schleife erfolglos, liefert sie „Lücke“ und links. Dieser Index bezeichnet genau die Stelle, an der der Suchwert eingefügt werden müsste, damit die Folge sortiert bleibt.