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? log₂ n Mal.
| n | Maximale Vergleiche (log₂ n) |
|---|
| 16 | 4 |
| 1.024 | 10 |
| 1.000.000 | 20 |
| 1 Mrd. | 30 |
Bei einer Milliarde Einträgen reichen 30 Vergleiche, das ist die Magie von O(log n).
Eigenschaften
- ✅ Brutal effizient: O(log n) ist fast wie O(1) in der Praxis
- ✅ 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)
Wann sinnvoll?
- Bei großen sortierten Arrays: hier ist binäre Suche ungeschlagen
- Bei vielen Suchanfragen: einmal sortieren, dann beliebig oft binär suchen
- Bei Datenbank-Indizes: B-Bäume nutzen binäre Suche pro Knoten
Java hat Arrays.binarySearch() und Collections.binarySearch() direkt eingebaut. Python's bisect Modul bietet das gleiche.