Binäre Suche: Ablauf, Beispiel und Laufzeit

Ein Array ist eine Reihe von Werten. Jeder Wert hat eine Nummer, den Index, und der Index beginnt bei 0. Ein Algorithmus ist eine Schritt-für-Schritt-Anleitung. Die binäre Suche ist ein Algorithmus, der in einem Array sehr effizient ein gesuchtes Element findet oder zuverlässig ausschließt, dass es vorhanden ist.

Voraussetzung ist, dass die Elemente sortiert sind. Hier sind die Werte von links nach rechts aufsteigend sortiert. Gleiche Werte dürfen mehrfach vorkommen. Kommt der Suchwert mehrmals vor, ist nicht festgelegt, welche Position ausgegeben wird.

Der Grund: Du vergleichst den Suchwert mit dem Wert in der Mitte. Weil die Folge sortiert ist, kannst du danach eine ganze Hälfte ausschließen. Ist der Suchwert kleiner als der Vergleichswert, kann er nur in der linken Hälfte stehen. Ist er größer, kann er nur in der rechten Hälfte stehen. Ohne Sortierung gilt dieser Schluss nicht. Die lineare Suche (sie geht der Reihe nach vor) hat dafür den Vorteil, auch in unsortierten Arrays zu funktionieren.

Noch zwei Bedingungen: Die Daten müssen bereits sortiert sein und so vorliegen, dass man direkt auf das n-te Element zugreifen kann. Und die Suche muss zur Sortierung passen.

Du arbeitest mit drei Zahlen: links, rechts und mitte. Die Zahlen links und rechts sind die Ränder des Suchbereichs, beide gelten einschließlich. Am Anfang umfasst der Suchbereich das komplette Array: links = 0 und rechts = len(folge) - 1. Dabei ist len(folge) die Anzahl der Elemente.

In jedem Schritt berechnest du die Mitte: mitte = links + (rechts - links) // 2. Das Zeichen // bedeutet: ganzzahlig teilen, also den Rest weglassen. Dann vergleichst du den Wert an der Position mitte mit dem Suchwert. Sind beide gleich, ist die Suche erfolgreich beendet und du gibst die Position mitte aus.

Ist der Suchwert kleiner als der Wert in der Mitte, schränkst du den rechten Rand ein: rechts = mitte - 1. Ist er größer, schränkst du den linken Rand ein: links = mitte + 1. Danach wiederholst du alles mit dem kleineren Suchbereich.

Warum rechnet man nicht einfach (links + rechts) // 2? In Sprachen mit begrenzten Ganzzahlen kann bei großen Arrays die Addition links + rechts zu einem Überlauf führen (die Zahl wird zu groß für den Datentyp). Deshalb wird links + (rechts - links) // 2 verwendet.

Ist der Suchbereich leer, wurde der Suchwert nicht gefunden. Die Suche ist erfolglos beendet. Im Beispielcode läuft die Schleife, solange links <= rechts gilt. Sobald links größer als rechts ist, ist der Suchbereich leer.

Der Beispielcode gibt dann „Lücke“ mit dem Wert von links zurück. Bei „Lücke x“ ist x der Index, an dem das gesuchte Element eingefügt werden müsste, damit die Folge sortiert bleibt. Andere Programme geben stattdessen einen Fehlercode zurück, möglicherweise ergänzt durch die Position, an der der Suchwert stehen würde.

Zum Aufwand: In jedem Schritt wird die Länge des Suchbereichs halbiert. Deshalb braucht man bei n Einträgen maximal ⌈log₂(n+1)⌉ Vergleichsschritte. Die Klammern ⌈ ⌉ bedeuten aufrunden. Die Zeitkomplexität sagt, wie stark der Aufwand wächst, wenn die Liste größer wird. Bei der binären Suche ist sie O(log n). Damit ist die binäre Suche deutlich schneller als die lineare Suche. Die Tabelle zeigt, wie langsam die Zahl der Vergleiche wächst.

In einer sortierten Liste mit 13 Buchstaben wären auch im schlechtesten Fall nur 4 Vergleiche nötig. Die lineare Suche müsste im ungünstigsten Fall bis zu 13 Elemente untersuchen. Der Vorteil fällt umso stärker ins Gewicht, je größer die Liste ist.