Binäre Suche

Die binäre Suche ist ein Algorithmus, der in einem Array sehr effizient ein gesuchtes Element entweder findet oder dessen Vorhandensein zuverlässig ausschließt. Voraussetzung ist, dass die Elemente in dem Array entsprechend einer totalen Ordnungsrelation angeordnet (sortiert) sind. Der Algorithmus basiert auf einer einfachen Form des Schemas „Teile und Herrsche“, zugleich stellt er auch einen Greedy-Algorithmus dar. Ordnung und spätere Suche müssen sich auf denselben Schlüssel beziehen: Beispielsweise kann in einem Telefonbuch, das nach Namen geordnet ist, mit binärer Suche nur nach einem bestimmten Namen gesucht werden, nicht jedoch z. B. nach einer bestimmten Telefonnummer.

Algorithmus Bearbeiten

Aufgabe: In einem sortierten Array soll ein Suchwert gefunden werden.

Eingabe:

Das zu durchsuchende Array, von links nach rechts mit aufsteigend sortierten Werten gefüllt. Die gleichen Werte dürfen mehrfach vorkommen.
Der Suchwert.

Ausgabe:

Wenn der Suchwert gefunden wurde, die Position des Suchwertes im Array.
Wenn der Suchwert mehrmals im Array vorkommt, ist nicht festgelegt, welche der möglichen Positionen ausgegeben wird.
Wenn der Suchwert nicht gefunden wurde, ein entsprechender Fehlercode, möglicherweise ergänzt durch die Position, an der der Suchwert stehen würde.

Ablauf:

Der Suchbereich umfasst anfangs das komplette Array.
Ist der Suchbereich leer, wurde der Suchwert nicht gefunden. Die Suche ist erfolglos beendet.
Die Mitte des Suchbereichs wird berechnet und der dort befindliche Wert mit dem Suchwert verglichen.
Ist der Suchwert gleich dem Vergleichswert, ist die Suche erfolgreich beendet. Die Position der Mitte wird ausgegeben.
Ist der Suchwert kleiner als der Vergleichswert, kann sich der Suchwert nur in der linken Hälfte befinden. Der rechte Rand des Suchbereichs wird auf die Position links von der Mitte eingeschränkt.
Ist der Suchwert größer als der Vergleichswert, kann sich der Suchwert nur in der rechten Hälfte befinden. Der linke Rand des Suchbereich wird auf die Position rechts von der Mitte eingeschränkt.
Die Suche wird mit dem verkleinerten Suchbereich ab Schritt 2 wiederholt.

Bei diesem Ablauf wird die Länge des Suchbereichs in jedem Schritt halbiert. Spätestens wenn der Suchbereich auf ein einzelnes Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor; dann ist als Ergebnis bekannt, wohin es einsortiert werden müsste.

Der Algorithmus zur binären Suche kann mittels Iteration oder Rekursion implementiert werden. Um ihn verwenden zu können, müssen die Daten bereits sortiert und in einer Datenstruktur vorliegen, in der direkt auf das n-te Element zugegriffen werden kann. Auf einer einfachen verketteten Liste würde die Effizienz verloren gehen (siehe aber Skip-Liste).

Beispiel Bearbeiten

Gesucht ist das Element mit dem Schlüssel G.
(Indizes und Rechnungen in grün;
\ ganzzahlige Division.)

Angenommen, in nebenstehender alphabetisch sortierter Liste von 13 Buchstaben möchte man wissen, ob der Buchstabe G in dieser Liste enthalten ist und an welcher Position er steht oder stehen müsste.

Hierzu prüft man zunächst das mittlere Element der Liste. Mittlere Position ist $13\backslash 2=6$ (' $\backslash$ ' ist Division mit Rest, hier: Teilen und Abrunden), es wird das Element an Position 6 mit dem gesuchten G verglichen. Dort findet man den Wert J. Da im Alphabet G vor J steht (also G kleiner als J ist) und die Liste ja sortiert ist, muss der Suchwert G im Bereich vor Position 6 stehen.

Das macht man nun rekursiv: Man durchsucht nicht den ganzen verbleibenden Bereich, sondern prüft wieder nur das Element in dessen Mitte, hier also das Element an der Position $6\backslash 2=3$ . Dort steht der Wert F. Da G größer als F ist, muss man im Bereich hinter dem F weitersuchen, jedoch vor dem J. Das heißt: man muss im Bereich zwischen Element 3 und Element 6 suchen.

Nun greift man wieder „in die Mitte“ dieses Bereiches zwischen F und J, an Position $({\textit {Position}}(F)+{\textit {Position}}(J))\,\backslash \,2=4$ . Dort finden wir nun das gesuchte Element G.

Wäre stattdessen der Suchwert I gewesen, dann hätten noch der Bereich zwischen G und J geprüft werden müssen. Dort ist H kleiner I; zwischen H und J verbleibt aber kein Bereich mehr, somit ist in dieser Liste kein I enthalten. Als Ergebnis kann der Algorithmus nur liefern, dass I hinter Position 5 einzusortieren wäre.

Die binäre Suche ist effizient: Von den insgesamt 13 Buchstaben mussten wir nur 3 Buchstaben vergleichen, bis wir den gesuchten Buchstaben G gefunden hatten. Auch im schlechtesten Fall hätten wir nur 4 Buchstaben vergleichen müssen.

Ein naiver Algorithmus würde hingegen einfach die ganze Liste von vorne nach hinten durchgehen und müsste somit im ungünstigsten Fall bis zu 13 Elemente untersuchen (wenn der Suchwert Z wäre, das ganz am Ende der Liste steht oder gar nicht in der Liste enthalten ist).

Mit binärer Suche kann man also die Anzahl der benötigten Vergleiche stark verringern. Dieser Vorteil fällt umso stärker ins Gewicht, je größer die zu durchsuchende Liste ist.

Komplexität Bearbeiten

Um in einem Array mit $n$ Einträgen die An- oder Abwesenheit eines Schlüssels festzustellen, werden maximal $\lceil \log _{2}(n+1)\rceil =\lfloor \log _{2}(n)+1\rfloor$ Vergleichsschritte benötigt. Somit hat die binäre Suche in der Landau-Notation ausgedrückt die Zeitkomplexität ${\mathcal {O}}(\log \ n)$ . Damit ist sie deutlich schneller als die lineare Suche, welche allerdings den Vorteil hat, auch in unsortierten Arrays zu funktionieren. In Spezialfällen kann die Interpolationssuche schneller sein als die binäre Suche.

Ähnliche Verfahren und Varianten Bearbeiten

Intervallschachtelung Bearbeiten

Das hier beschriebene binäre Suchverfahren kann als eine (endliche) Ausprägung der Intervallschachtelung aus der mathematischen Analysis angesehen werden.

Binärer Suchbaum Bearbeiten

Der Such-Algorithmus entspricht auch der Suche in einem binären Suchbaum, wenn man das Array als solchen interpretiert: das mittlere Element ist die Wurzel, die Mitten der so entstehenden Hälften die Wurzeln der entsprechenden Teilbäume und so fort. Der aus dieser Interpretation resultierende Binärbaum ist sogar ein sog. vollständig balancierter Binärbaum, also ein Binärbaum, bei dem die Längen der Pfade von den Blättern zur Wurzel sich um höchstens 1 unterscheiden. Das gilt auch unabhängig von der Richtung der Rundung bei der Bildung des Mittelwerts der Indizes.^[1] Der so entstandene Binärbaum ist (wie die binäre Suche) unter allen Binärbäumen mit $n$ Elementen optimal in Bezug auf

die maximale Pfadlänge $h:=\lceil \log _{2}(n+1)\rceil$ (= Höhe des Baums),
die Pfadlängensumme, die sich zu $1+(n+1)h-2^{h}$ ergibt, und
die mittlere Pfadlänge.

Letztere entspricht der mittleren Anzahl von Vergleichen, wenn alle Elemente gleich wahrscheinlich sind.

Teilt man nicht in der Mitte, so ist das Ergebnis immer noch ein binärer Suchbaum, jedoch ist er u. U. nicht balanciert und nicht optimal.

Die große Überlegenheit des binären Suchbaums gegenüber der binären Suche im Array liegt erstens im besseren Verhalten bei Einfügungen und Löschungen, bei denen im Mittel ein linearer Aufwand anfällt. Bei Bäumen gibt es auch in diesen Fällen Implementierungen mit garantiert logarithmischer Laufzeit. Dort ist auch die Speicherverwaltung einfacher, da Änderungen nicht das ganze Array betreffen, sondern sich mit dem Entstehen oder Verschwinden eines Elementes direkt verbinden lassen. Zweitens können Bäume besser als das Array an Häufigkeiten angepasst werden. Wenn aber das Array schon fertig sortiert ist und sich dann nicht mehr ändert und Zugriffswahrscheinlichkeiten keine Rolle spielen, ist das Array ein gutes Verfahren.

Binäre Suche und totale Quasiordnung Bearbeiten

Da das Array als endlicher Definitionsbereich einer Funktion angesehen werden kann, die natürlich nicht notwendigerweise injektiv sein muss, lässt sich das Vorkommen von Duplikaten leicht über die Funktionswerte regeln. Und wenn die Ordnungsrelation von vornherein schon keine Totalordnung, sondern nur eine totale Quasiordnung ist, ist es ggf. sparsamer, die Äquivalenzklassen vor dem Vergleichen zu bilden, als alle möglichen Duplikate im Array zu halten.

Beispiel

In einer Sammlung von Schlüsselwörtern soll zwar Groß- und Kleinschreibung zulässig sein, die Schlüsselwörter sollen sich aber in ihrer Bedeutung nicht unterscheiden.

Interpolationssuche Bearbeiten

Bei der Interpolationssuche wird das Array nicht mittig geteilt, sondern per linearer Interpolation die Position des gesuchten Elementes abgeschätzt. Sind die Schlüssel in etwa äquidistant verteilt, so kann das gesuchte Element in nahezu konstanter Zeit gefunden werden. In einem ungünstigen Fall wird die Laufzeit jedoch linear. Abgesehen davon muss der Definitionsbereich sich für eine lineare Interpolation eignen.

Quadratische Binärsuche Bearbeiten

Bei der quadratischen Binärsuche versucht man die Vorteile der Interpolationssuche mit denen der normalen Binärsuche zu kombinieren und mittels Interpolation in jeder Iteration den Suchraum auf ein Intervall der Länge ${\sqrt {n}}$ zu verkleinern.

Implementierung Bearbeiten

In zahlreichen Programmiersprachen wird dieser Algorithmus bereits mitgeliefert. In Java gibt es beispielsweise java.util.Arrays.binarySearch, in Python das Paket bisect, in C++/STL gibt es std::binary_search.

Als Rückgabewert wird die Arrayposition zurückgegeben, an der der gesuchte Eintrag gefunden wurde. Konnte der Eintrag nicht gefunden werden, wird meist die Position zurückgegeben, an der er stehen müsste, von −1 ausgehend rückwärts gezählt.

Bei großen Arrays kann die Berechnung der Mittenposition mittels „(links + rechts) ÷ 2“ bei der Addition zu einem Überlauf führen, daher wird stattdessen „links + (rechts - links) ÷ 2“ verwendet.

Wenn sowohl der linke als auch der rechte Rand des Suchbereichs einschließlich gelten, kann während der Suche die Mittenposition 0 werden und der nächste Wert für den rechten Rand negativ werden. Würde man hier einen vorzeichenlosen Datentyp verwenden, fände ein Unterlauf statt und die Bedingung der Schleife würde erfüllt bleiben (Endlosschleife).

Im folgenden Beispielcode in Python gelten beide Ränder des Suchbereichs einschließlich. Die Suchfunktion liefert entweder „Position X“ oder „Lücke X“, je nachdem, ob der Suchwert gefunden wurde oder nicht.

def binäre_suche(folge: Sequence[int], x: int) -> Tuple[str, int]:
    links = 0
    rechts = len(folge) - 1

    while links <= rechts:
        mitte = links + (rechts - links) // 2  # Bereich halbieren
        if folge[mitte] == x:
            return 'Position', mitte

        if folge[mitte] > x:
            rechts = mitte - 1  # im linken Abschnitt weitersuchen
        else:
            links = mitte + 1  # im rechten Abschnitt weitersuchen

    return 'Lücke', links

Anmerkungen Bearbeiten

↑ Bei einer Belegung des Arrays mit $n=2^{h}-1$ Einträgen (das entspricht einem vollständigen Binärbaum der Höhe $h$ ) haben alle Halbierungen einen Divisionsrest von 0.

[1] Bei einer Belegung des Arrays mit $n=2^{h}-1$ Einträgen (das entspricht einem vollständigen Binärbaum der Höhe $h$ ) haben alle Halbierungen einen Divisionsrest von 0.

[1]