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:

int n = 1_000_000;
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;


int comparisons = 0;
int found = -1;
for (int i = 0; i < n; i++) {
    comparisons++;
    if (prices[i] == target) {
        found = i;
        break;
    }
}
System.out.println("Index: " + found);
System.out.println("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

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}
int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58};
System.out.println("Index: " + find(prices, 49));
Ausgabe
Index: 12

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (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 - lo) / 2, nicht (lo + hi) / 2. Beide ergeben dieselbe Zahl, aber die zweite kann überlaufen. Warum, steht auf einer der nächsten Karten.
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?

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;


int steps = 0;
int lo = 0;
int hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    steps++;
    if (prices[mid] == target) {
        break;
    } else if (prices[mid] < target) {
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}
System.out.println(steps);
Antwort

Probier es aus

Ergänze

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

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (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:

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    int probes = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        System.out.println("lo=" + lo + " hi=" + hi + " mid=" + mid);
        if (++probes == 8) {
            System.out.println("Ich höre nach 8 Versuchen auf: lo und hi bewegen sich nicht");
            return -1;
        }
        if (prices[mid] == target) {
            return mid;
        } else if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return -1;
}
int[] 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:

int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58};
System.out.println("Index: " + find(prices, 58));
Ausgabe
Index: -1

Wähle die Zeile mit dem Fehler.

Die Idee

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

Ein int in Java reicht bis 2.147.483.647. Ein Array mit mehr als einer Milliarde Elementen ist selten, kommt aber vor: ein Dateiindex, ein Log, eine In-Memory-Datenbank. Dann kann lo + hi die Grenze überschreiten:

int lo = 1_500_000_000;
int hi = 2_000_000_000;
System.out.println((lo + hi) / 2);
System.out.println(lo + (hi - lo) / 2);
System.out.println((lo + hi) >>> 1);
Ausgabe
-397483648
1750000000
1750000000

Die Summe ist 3.500.000.000. Sie passt nicht in einen int, und Java meldet keinen Fehler: Es wickelt sie in eine negative Zahl um. Die Mitte wird -397.483.648, und der Index -397.483.648 löst eine Exception aus. lo + (hi - lo) / 2 rechnet dasselbe ohne Addition: Die Differenz passt immer. (lo + hi) >>> 1 ist der andere Weg: >>> schiebt die Bits nach rechts und behandelt die Zahl als nicht negativ, und das ist die Division durch 2.

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:

static int lowerBound(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}
int[] prices = {3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49};
System.out.println("find: " + find(prices, 15));
int first = lowerBound(prices, 15);
System.out.println("Die erste 15 €: Index " + first);
System.out.println("Produkte zu 15 €: " + (lowerBound(prices, 16) - first));
int from20 = lowerBound(prices, 20);
System.out.println("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.

Java hat eine fertige binäre Suche: Arrays.binarySearch für ein Array und Collections.binarySearch für eine sortierte List. Ist der Preis nicht da, liefert sie -(der Platz, wo er hingehören würde) - 1, sodass die negative Zahl auch verrät, wo dieser Platz ist:

int[] prices = {3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49};
System.out.println(Arrays.binarySearch(prices, 24));
int i = Arrays.binarySearch(prices, 20);
System.out.println(i);
System.out.println(-i - 1);
System.out.println(Arrays.binarySearch(prices, 15));
Ausgabe
8
-9
8
5

Bei Duplikaten liefert Arrays.binarySearch einen der gleichen, ohne zu versprechen, welchen: Für 15 € gibt es 5, während der erste bei 4 liegt. Für die untere Schranke schreibst du eine eigene Methode, etwa lowerBound.

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.
static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (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 upperBound: 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 ·