Die binäre Suche, auch Halbierungsprinzip, wird verwendet um in sortierten Folgen ein Element zu suchen.
Idee
- Menge Sortieren
- Median mit Suchelement vergleichen:
- Bei Gleichheit wurde das Element gefunden
- Ist das Element kleiner bzw. größer, wird der Median der linken bzw. rechten Hälfte genommen und die Schritte wiederholt
Laufzeit
Die Laufzeit zum Vorbereiten (Sortieren) ergibt sich aus der unteren Schranke für vergleichsbasiertes Sortieren:
Die Binäre Suche selbst hat dann eine Laufzeit von: