Zum Inhalt
wannacode

Binäre Suche

Kurz gesagt: Die binäre Suche findet einen Wert in einem sortierten Array, indem sie mit der Mitte vergleicht und jedes Mal die Hälfte verwirft: O(log n) Vergleiche.

Problem

Der Filter, der den ganzen Katalog liest

Der Shop hat 1.000.000 Produkte, und die Preisliste ist nach Preis sortiert. Der Filter „genauer Preis“ sucht mit einer Schleife von vorn, wie die lineare Suche. Die Preise im Code stehen in Euro-Cent: von 2 bis 2.000.000. Ein Kunde sucht ein Produkt zu 20.000,01 €, und es gibt keins:

n = 1_000_000
prices = [2 * (i + 1) for i in range(n)]
target = 2 * n + 1


comparisons = 0
found = -1
for i in range(n):
    comparisons += 1
    if prices[i] == target:
        found = i
        break
print(f"Index: {found}")
print(f"Vergleiche: {comparisons}")
Ausgabe
Index: -1
Vergleiche: 1000000

Eine Million Vergleiche, um „keins“ zu sagen. Und bei jedem Öffnen der Seite läuft der Filter für Dutzende Preise.

Die Preise sind sortiert, und die Schleife nutzt das nicht. Wenn du ein Wort im Wörterbuch nachschlägst, liest du nicht ab der ersten Seite. Du schlägst es in der Mitte auf und siehst, ob das Wort davor oder danach kommt.

Die Idee

Frag die Mitte, wirf die Hälfte weg

Schau dir den Preis in der Mitte der Preisliste an:

  • Ist es der gesuchte, bist du fertig;
  • ist er kleiner, kann der gesuchte nur rechts liegen. Die linke Hälfte fällt weg, samt der Mitte;
  • ist er größer, kann der gesuchte nur links liegen.

Dann dasselbe mit der Hälfte, die übrig ist. Das ist die binäre Suche. Den Bereich, in dem der Preis noch liegen kann, halten zwei Indizes fest: lo (der Anfang) und hi (das Ende). Die Mitte ist mid.

Jeder Vergleich halbiert den Bereich. Aus 1.000.000 Preisen werden 500.000, dann 250.000, und nach etwa 20 Halbierungen bleibt einer übrig. Wie oft du durch 2 teilst, bis du bei 1 bist, heißt Logarithmus zur Basis 2: log₂ 1.000.000 ≈ 20. Deshalb ist die binäre Suche O(log n) und die lineare O(n).

Eine Bedingung gibt es: Das Array muss sortiert sein. In einem unsortierten Array stimmt „er ist kleiner, also liegt er rechts“ nicht.

Sieh es dir an

lo, mid und hi in der Preisliste

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]
print(f"Index: {find(prices, 49)}")
Ausgabe
Index: 12

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
Schritt für Schritt, in Worten
  1. Die Preisliste ist sortiert: 15 Preise. Wir suchen 49 €. lo und hi umfassen alles, von 0 bis 14.
  2. mid = 7: 27 € < 49 €, also liegt der Preis rechts. lo = 8, der linke Teil fällt weg. Es bleiben 7 Preise übrig.
  3. mid = 11: 44 € < 49 €, also liegt der Preis rechts. lo = 12, der linke Teil fällt weg. Es bleiben 3 Preise übrig.
  4. mid = 13: 53 € > 49 €, also liegt der Preis links. hi = 12, der rechte Teil fällt weg. Es bleibt 1 Preis übrig.
  5. mid = 12: 49 €. Das ist der gesuchte Preis: find liefert 12.
  6. 4 Vergleiche. Eine Suche von vorn hätte 13 Preise angesehen; bei 1 000 000 Preisen braucht die binäre Suche höchstens 20.
Die Mitte ist (lo + hi) // 2: // teilt und rundet auf eine ganze Zahl ab. In Java und C# schreibt man es anders, weil dort die Summe überlaufen kann. In Python kann sie das nicht: Eine der nächsten Karten sagt, warum.
Genauer, für Neugierige

Der schlechteste Fall ist, dass der Preis nicht da ist: Der Bereich wird halbiert, bis lo an hi vorbeigeht. Bei n Preisen sind das höchstens ⌊log₂ n⌋ + 1 Vergleiche: 4 bei 10 Preisen, 10 bei 1000, 20 bei 1.000.000. Der beste Fall ist ein Vergleich: Der Preis liegt genau in der Mitte.

Ein „Vergleich“ ist hier eine Probe von mid. Die Prüfung auf gleich und die Prüfung auf kleiner sind zwei Zeilen im Code, aber sie fragen nach demselben Preis.

Probier es aus

Sage voraus, wie viele Proben

Sortierte Preise in Euro-Cent: 2, 4, 6, …, 2000. Wir suchen 2001, und diesen Preis gibt es nicht. Wie oft läuft die Schleife?

n = 1000
prices = [2 * (i + 1) for i in range(n)]
target = 2 * n + 1


steps = 0
lo = 0
hi = n - 1
while lo <= hi:
    mid = (lo + hi) // 2
    steps += 1
    if prices[mid] == target:
        break
    elif prices[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(steps)
Antwort

Probier es aus

Ergänze

Der Preis bei mid ist kleiner als der gesuchte. Wo beginnt der neue Bereich?

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = 
        else:
            hi = mid - 1
    return -1

Die Idee

Die Grenzen: wo jeder Fehler macht

Die binäre Suche braucht sechs Zeilen und ist dafür bekannt, dass man sie falsch schreibt. Der Fehler ist fast immer um eins daneben: < statt <=, mid statt mid - 1. Man nennt das einen Off-by-one-Fehler.

Davor schützt eine Entscheidung: Was bedeuten lo und hi? Danach hältst du dich überall daran.

  • Geschlossener Bereich [lo, hi]: Beide Enden dürfen der gesuchte Preis sein. hi beginnt beim letzten Index, die Schleife läuft, solange lo <= hi, und die Mitte wirfst du mit hi = mid - 1 und lo = mid + 1 weg. Das ist das find von oben.
  • Halboffener Bereich [lo, hi): hi ist der erste Platz nach dem Bereich. hi beginnt bei der Länge des Arrays, die Schleife läuft, solange lo < hi, und nach links gehst du mit hi = mid, denn hi gehört ohnehin nicht zum Bereich.

Beides ist richtig. Der Fehler ist, sie zu vermischen. Hier ein geschlossener Bereich mit hi = mid aus dem halboffenen. Wir suchen 4 €, und diesen Preis gibt es nicht. Eine Sicherung stoppt die Schleife nach 8 Proben; sonst würde sie nie enden:

def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    probes = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        print(f"lo={lo} hi={hi} mid={mid}")
        probes += 1
        if probes == 8:
            print("Ich höre nach 8 Versuchen auf: lo und hi bewegen sich nicht")
            return -1
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1
prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]
find(prices, 4)
Ausgabe
lo=0 hi=14 mid=7
lo=0 hi=7 mid=3
lo=0 hi=3 mid=1
lo=0 hi=1 mid=0
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
Ich höre nach 8 Versuchen auf: lo und hi bewegen sich nicht

Wenn lo und hi beide 1 werden, ist die Mitte 1, der Preis dort ist 5 €, mehr als 4 €, und hi = mid ist wieder 1. Nichts ändert sich. Das ist eine Endlosschleife: Das Programm stürzt nicht ab, es hängt.

Probier es aus

Finde den Fehler

Die Suche findet 49 €, aber nicht das teuerste Produkt, 58 €, obwohl es in der Preisliste steht:

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58]
print(f"Index: {find(prices, 58)}")
Ausgabe
Index: -1

Wähle die Zeile mit dem Fehler.

Die Idee

Wenn (lo + hi) / 2 überläuft

In Java und C# reicht ein int bis 2.147.483.647, und bei einem Array mit mehr als einer Milliarde Elementen läuft (lo + hi) / 2 über: Die Summe wird zu einer negativen Zahl. Deshalb schreibt man dort die Mitte als lo + (hi - lo) / 2.

In Python haben ganze Zahlen keine Obergrenze. Die Summe ist eine größere Zahl, nichts weiter:

lo = 1_500_000_000
hi = 2_000_000_000
print((lo + hi) // 2)
print(lo + (hi - lo) // 2)
Ausgabe
1750000000
1750000000

(lo + hi) // 2 stimmt bei jeder Größe. lo + (hi - lo) // 2 funktioniert auch, schützt hier aber vor nichts.

Genauer, für Neugierige

Der Fehler ist nicht ausgedacht. Die binäre Suche in der Java-Standardbibliothek, Arrays.binarySearch, hatte neun Jahre lang (low + high) / 2. Joshua Bloch beschrieb das 2006 im Artikel „Nearly All Binary Searches and Mergesorts are Broken“: Ein Programm mit einem Array von mehr als 2³⁰ Elementen stürzt mit ArrayIndexOutOfBoundsException ab. Heute steht dort (low + high) >>> 1.

Sieh es dir an

Der erste Preis ab 20 €

Der Filter „Preis ab 20 €“ sucht keinen genauen Preis. Er sucht den ersten Platz, an dem der Preis mindestens 20 € beträgt: Ab dort stehen alle Produkte, die er anzeigen muss. Das heißt untere Schranke (Lower Bound). Sie ist auch das erste Vorkommen: Kommt in den Preisen dreimal 15 € vor, ist die untere Schranke von 15 die erste davon.

find liefert sie nicht: Es hält bei der ersten 15 an, auf die es trifft. Die untere Schranke nutzt einen halboffenen Bereich, und die Schleife hält bei Gleichheit nicht an, sie geht weiter nach links:

def lower_bound(prices, target):
    lo = 0
    hi = len(prices)
    while lo < hi:
        mid = (lo + hi) // 2
        if prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49]
print(f"find: {find(prices, 15)}")
first = lower_bound(prices, 15)
print(f"Die erste 15 €: Index {first}")
print(f"Produkte zu 15 €: {lower_bound(prices, 16) - first}")
from20 = lower_bound(prices, 20)
print(f"Der erste Preis ab 20 €: {prices[from20]} €")
Ausgabe
find: 5
Die erste 15 €: Index 4
Produkte zu 15 €: 3
Der erste Preis ab 20 €: 24 €

Ist der Preis kleiner als der gesuchte, fällt er samt allem davor weg: lo = mid + 1. Sonst kann mid die Antwort sein, also bleibt es im Bereich: hi = mid. Die Schleife endet, wenn sich lo und hi treffen, und dort ist der erste Platz mit einem Preis ≥ dem gesuchten. Gibt es keinen solchen Platz, ist lo die Länge des Arrays. Wie viele Produkte 15 € kosten, ist die Differenz zweier unterer Schranken: der von 16 und der von 15.

In Python gibt es die untere Schranke fertig: das Modul bisect. bisect_left ist genau das lower_bound von oben, und bisect_right liefert den ersten Platz mit einem Preis, der größer ist als der gesuchte:

import bisect


prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49]
print(bisect.bisect_left(prices, 24))
print(bisect.bisect_left(prices, 20))
print(bisect.bisect_left(prices, 15))
print(bisect.bisect_right(prices, 15))
Ausgabe
8
8
4
7

bisect_right(prices, 15) - bisect_left(prices, 15) ist die Zahl der Produkte zu 15 €. Ob der genaue Preis da ist, prüfst du so: i < len(prices) and prices[i] == x. bisect.insort setzt ein neues Element an seinen Platz in einer sortierten Liste.

Sieh es dir an

Miss es: linear gegen binär

Lineare und binäre Suche in derselben sortierten Preisliste, wenn der Preis nicht da ist. Die lineare Suche vergleicht jeden Preis: n Vergleiche. Die binäre Suche macht bei 1.000.000 Preisen 20 Vergleiche:

  • Lineare Suche (jeder Preis) O(n)
  • Binäre Suche O(log n)
Algorithmusn = 10n = 1.000n = 100.000n = 1.000.000
Lineare Suche (jeder Preis)101.000100.0001.000.000
Binäre Suche4101720
Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.
def find(prices, target):
    lo = 0
    hi = len(prices) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if prices[mid] == target:
            return mid
        elif prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Die binäre Kurve liegt fast flach: Bei 100-mal so vielen Preisen steigt sie um etwa 7 Vergleiche. Deshalb ist die binäre Suche überall, wo etwas sortiert ist: Datenbankindizes, git bisect, das Finden der Version, ab der ein Test fehlschlägt.

Übung

Der Preisfilter: von 10 € bis 30 €

Löse die Aufgabe in deinem Editor.

Von 10 € bis 30 €. Der Filter zeigt, wie viele Produkte von 10 € bis einschließlich 30 € kosten. Die Preisliste ist sortiert: 3 €, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44 und 49. Geh nicht das ganze Array durch: Finde mit zwei binären Suchen den ersten Platz mit einem Preis ≥ 10 € und den ersten mit einem Preis ≥ 31 €. Die Differenz ist die Anzahl.

Ausgabe
Von 10 € bis 30 €: 7 Produkte

Weitere Aufgaben

  • Das letzte Vorkommen. Schreibe upper_bound: den ersten Platz mit einem Preis, der größer ist als der gesuchte. Das letzte Produkt zu 15 € steht einen Platz davor.
  • Ein freier Lieferslot. Die freien Lieferslots sind ein sortiertes Array von Minuten nach Mitternacht (540 ist 9:00 Uhr). Der Kunde möchte die Lieferung nicht vor 14:10 Uhr. Finde den ersten freien Slot oder sage, dass es keinen gibt.
  • Wohin der neue Preis gehört. Ein neues Produkt zu 21 € muss so in die Preisliste, dass sie sortiert bleibt. Finde den Platz mit binärer Suche.

Test

Teste dich

1. Die Preisliste hat 1.000.000 Preise, nach Größe sortiert. Wie viele Vergleiche macht die binäre Suche höchstens?
2. Der Bereich ist geschlossen: hi beginnt beim letzten Index. Welche Schleifenbedingung stimmt?
3. Bei while (lo <= hi) schreibt jemand hi = mid statt hi = mid - 1. Was passiert?
4. In den Preisen kommt dreimal 15 € vor. Welchen Platz suchst du, um jedes Produkt „ab 15 €“ anzuzeigen?
5. Die Produktliste ist nicht sortiert. Kannst du die binäre Suche benutzen?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·