Binäre Suche.

Binäre Suche halbiert bei jedem Schritt den Suchraum, indem sie das mittlere Element prüft und entscheidet ob der Suchwert davor oder danach liegt. Funktioniert nur auf sortierten, effizient indexierbaren Datenstrukturen wie Arrays (bei LinkedLists ist der Indexzugriff selbst O(n)). Du lernst hier die Halbierungs-Logik mit low/mid/high-Variablen-Trace, die Komplexität lceil log₂(n+1) rceil Vergleiche im Worst Case (egal ob Element gefunden wird oder nicht), die Overflow-Falle bei mid = (low + high) / 2 und die sichere Alternative mid = low + (high - low) / 2, die Abbruchbedingung while (low <= high) und warum bei n=1024 im Worst Case bzw. bei erfolgloser Suche bis zu 11 Prüfungen möglich sind (lceil log₂(1025) rceil = 11) und bei erfolgreichem Treffer weniger, plus die Bibliotheks-Varianten lower_bound/upper_bound (C++) bzw. bisect_left/bisect_right (Python) für erstes/letztes Vorkommen bei Duplikaten.

Was du in der Klausur können musst:

• Idee: mittleres Element anschauen, Suchwert kleiner = links weitersuchen, größer = rechts, gleich = gefunden
• Komplexität: O(log n) im Worst- und Average-Case, O(1) im Best-Case
• Voraussetzung: Array muss sortiert sein, sonst funktioniert es nicht
• Anwendung: bei großen sortierten Datenmengen (1 Mio Einträge → ca. 20 Vergleiche statt 500.000)

In Klausuren oft gefragt: dokumentiere die Suche Schritt für Schritt für ein gegebenes Array und einen Suchwert. Schreibe pro Iteration die aktuellen low/high/mid-Indizes auf, das ist die Standard-Aufgabenform.

Die Idee

Stell dir vor, du suchst eine Seite in einem Wörterbuch:

Du schlägst nicht Seite 1 auf und blätterst durch. Du schlägst in der Mitte auf, schaust ob das gesuchte Wort davor oder dahinter steht, und wiederholst das Halbieren.

Das ist binäre Suche. Bei jeder Halbierung verringert sich die Suchmenge um 50%, daher die Komplexität O(log n).

Voraussetzung: sortiert

Binäre Suche funktioniert nur auf sortierten Arrays. Ist das Array unsortiert:

• einzelne Suche: meist linear suchen (eine O(n)-Suche ist günstiger als O(n log n) Sortieren).
• viele Suchen auf demselben Array: einmaliges Sortieren O(n log n) amortisiert sich, danach k · O(log n) pro weitere Suche.

Inline-Trace für Target 23 (sortiertes 10er-Array)

Bevor wir den Code anschauen, das Halbierungs-Prinzip in der Mini-Tabelle. Array [2, 5, 9, 14, 18, 23, 27, 31, 36, 42] (Indizes 0..9), Target 23:

Drei Vergleiche bei n = 10. Worst Case wäre lceil log₂ 11 rceil = 4.

Implementierung

public static int binarySearch(int[] arr, int target) {
    int lo = 0;
    int hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

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

Komplexität

Bei jeder Iteration halbiert sich der Suchraum:

n → n/2 → n/4 → n/8 → dots → 1

Wie oft kann man n halbieren bis man bei 1 ankommt? Größenordnung log₂ n. Exakt im Worst Case (auch bei "nicht gefunden") sind es lceil log₂(n+1) rceil Vergleiche bzw. lfloor log₂ n rfloor + 1 bei vorhandenem Treffer.

Bei einer Milliarde Einträgen reichen 30 Vergleiche, das ist die Magie von O(log n). Faustregel in Klausuren: ungefähr log₂ n.

Eigenschaften

• ✅ Sehr effizient: O(log n) wächst sehr langsam und skaliert auch bei Millionen Einträgen gut.
• ✅ Skaliert auch bei Millionen: 30 Vergleiche reichen bei 1 Mrd. Elementen
• ❌ Verlangt sortiertes Array: einmaliges Sortieren kostet O(n log n)
• ❌ Nicht für verkettete Listen: braucht Random-Access in O(1)

Klausur-Trace: binäre Suche Schritt für Schritt

Die Standard-Klausuraufgabe lautet: "Gegeben das sortierte Array, gesucht ist Target x. Trage low, high und mid pro Iteration ein." Wir gehen drei Varianten durch.

Beispiel A: Treffer in der Mitte (Best Case)

Array [1, 4, 7, 9, 12, 15, 18] (Indizes 0..6), gesucht Target 9.

Ein einziger Vergleich. Best Case O(1).

Beispiel B: Treffer am Rand (typischer Fall)

Gleiches Array, gesucht Target 15.

Zwei Vergleiche. Bei n=7 wären lceil log₂(8) rceil = 3 Vergleiche der Worst Case.

Beispiel C: Target nicht im Array (erfolglose Suche)

Gleiches Array, gesucht Target 6.

Jetzt ist low (2) > high (1), die while-Bedingung low <= high ist verletzt → return -1. Drei Vergleiche, das ist der Worst Case bei n=7.

Achtung Klausur: bei n=1024 sind im Worst Case bzw. bei erfolgloser Suche bis zu 11 Prüfungen möglich (lceil log₂(1025) rceil = 11), bei erfolgreichem Treffer können es weniger sein.

Rekursiv vs. iterativ

Die obige Implementierung ist iterativ. Rekursiv sieht es so aus:

public static int bsRecursive(int[] arr, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return bsRecursive(arr, target, mid + 1, hi);
    return bsRecursive(arr, target, lo, mid - 1);
}

In der Klausur wird oft die iterative Variante verlangt, weil sie keinen Rekursionsstack braucht. Beide Varianten haben identische Komplexität O(log n), die iterative aber O(1) Zusatzspeicher gegen O(log n) Rekursionsstack bei der rekursiven Form.

Duplikate

Die Standard-Variante findet irgendeinen passenden Index, nicht zwingend den ersten oder letzten. Für erstes Vorkommen → lower_bound / bisect_left; für letztes Vorkommen → upper_bound / bisect_right.

Wann sinnvoll?

• Bei großen sortierten Arrays: hier ist binäre Suche deutlich besser als lineare Suche. Für sehr viele exakte Lookups können Hash-Strukturen mit durchschnittlich O(1) noch besser sein, dafür ohne sortierte Traversierung.
• Bei vielen Suchanfragen: einmal sortieren, dann beliebig oft binär suchen
• Bei Datenbank-Indizes: B-Bäume/B+-Bäume nutzen sortierte Schlüssel und eine logarithmische Baumstruktur. Innerhalb eines Knotens kann je nach Implementierung linear oder binär gesucht werden, der Hauptvorteil kommt aus der hohen Verzweigung und der geringen Baumhöhe, nicht aus der binären Suche pro Knoten.

Bibliotheken:

• Java: Arrays.binarySearch() und Collections.binarySearch() setzen sortierte Daten voraus, bei unsortierten Daten ist das Ergebnis undefiniert. Bei Duplikaten ist nicht garantiert, welcher passende Index zurückgegeben wird.
• Python: bisect liefert primär Einfügepositionen in sortierten Listen (bisect_left, bisect_right). Für Existenzprüfung danach: pos < len(a) and a[pos] == target.
• C++: std::binary_search liefert nur bool. Für die Position: std::lower_bound (erstes Element ≥ Target).

Binäre Suche live

Beobachte wie sich der Suchbereich halbiert. Der orange Highlight markiert das aktuelle Mittelpunkt-Element. Werte außerhalb des Suchbereichs werden ausgegraut.

Probier folgendes:

• Setz das Target auf einen Wert genau in der Mitte: 1 Vergleich (Best Case)
• Setz das Target auf einen Wert außerhalb des Arrays: lceil log₂(n+1) rceil Vergleiche (Worst Case)
• Größenordnung: bei n=16 ungefähr 4–5 Vergleiche, bei n=32 ungefähr 5–6

Halt fest: jede Verdopplung der Eingabe kostet nur einen zusätzlichen Vergleich.

Faustregel zum Mitnehmen: Binäre Suche skaliert logarithmisch. Bei 1 Million Einträgen reichen ~20 Vergleiche, bei 1 Milliarde ~30. Linear bräuchte 1 Million bzw. 1 Milliarde.

---

Code-Stepper: Binäre Suche mit low/mid/high

Wir suchen die 23 im sortierten Array [2, 5, 9, 14, 18, 23, 27, 31, 36, 42] (10 Elemente). Du siehst wie sich low und high nach jedem Vergleich auf eine Seite verschieben, und der Suchbereich halbiert sich. Maximal lceil log₂(11) rceil = 4 Vergleiche.