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.
| n | Maximale Vergleiche lceil log₂(n+1) rceil |
|---|
| 16 | 5 |
| 1.024 | 11 |
| 1.000.000 | 20 |
| 1 Mrd. | 30 |
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.
| Iter | low | high | mid | arr[mid] | Aktion |
|---|
| 1 | 0 | 6 | 3 | 9 | Treffer, return 3 |
Ein einziger Vergleich. Best Case O(1).
Beispiel B: Treffer am Rand (typischer Fall)
Gleiches Array, gesucht Target 15.
| Iter | low | high | mid | arr[mid] | Aktion |
|---|
| 1 | 0 | 6 | 3 | 9 | 9 < 15 → low = mid+1 = 4 |
| 2 | 4 | 6 | 5 | 15 | Treffer, return 5 |
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.
| Iter | low | high | mid | arr[mid] | Aktion |
|---|
| 1 | 0 | 6 | 3 | 9 | 9 > 6 → high = mid-1 = 2 |
| 2 | 0 | 2 | 1 | 4 | 4 < 6 → low = mid+1 = 2 |
| 3 | 2 | 2 | 2 | 7 | 7 > 6 → high = mid-1 = 1 |
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.
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).
