Binäre Suche
Halbiert in jedem Schritt den Suchbereich, indem die Mitte mit dem Zielwert verglichen wird.
- Vergleiche 0
- Ergebnis noch offen
- aktiver Bereich
- Mitte
- Treffer
- ausgeschlossen
Pseudocode
1 lo = 0; hi = n - 1
2 while lo <= hi
3 mid = (lo + hi) / 2
4 if a[mid] == target: return mid
5 if a[mid] < target: lo = mid + 1
6 else: hi = mid - 1
7 return -1
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Die binäre Suche setzt ein sortiertes Array voraus und nutzt diese Sortierung, um den Suchbereich in jedem Schritt zu halbieren. Sie merkt sich die Grenzen lo und hi des aktuellen Bereichs und berechnet die Mitte mid. Dann vergleicht sie a[mid] mit dem Zielwert: ist beides gleich, ist der Treffer gefunden; ist a[mid] kleiner, kann der gesuchte Wert nur rechts liegen und lo wird auf mid+1 gesetzt; ist a[mid] größer, geht die Suche links weiter und hi wird auf mid-1 gesetzt. Sobald lo > hi gilt, ist der Bereich leer und der Wert nicht im Array. Da sich der Suchbereich pro Iteration halbiert, sind höchstens log2(n)+1 Schritte nötig. Das ergibt eine logarithmische Laufzeit O(log n) im Average und Worst Case; im Best Case sitzt der Treffer direkt in der ersten Mitte (O(1)). Der Zusatz-Speicher ist konstant (O(1)). Voraussetzung bleibt: das Array muss sortiert sein und Random-Access erlauben. Der Visualizer sortiert die Eingabe deshalb automatisch.
Komplexität
- Best Case
O(1) - Average Case
O(log n) - Worst Case
O(log n) - Zusatz-Speicher
O(1)
Wann verwenden?
Erste Wahl, sobald die Daten sortiert sind und Random-Access erlaubt ist, also etwa ein Array im Speicher oder eine indexierte Spalte in einer Datenbank. Klassische Lösung für schnelle Lookups in großen, überwiegend statischen Datensätzen.