Ternäre Suche
Teilt den Suchbereich in drei Drittel und vergleicht an zwei Drittel-Punkten.
- Vergleiche 0
- Ergebnis noch offen
- Vergleich
- Tausch
- sortiert
Pseudocode
1 lo = 0; hi = n - 1
2 while lo <= hi
3 m1 = lo + (hi - lo) / 3
4 m2 = hi - (hi - lo) / 3
5 if a[m1] == target: return m1
6 if a[m2] == target: return m2
7 if target < a[m1]: hi = m1 - 1
8 else if target > a[m2]: lo = m2 + 1
9 else: lo = m1 + 1; hi = m2 - 1
10 return -1
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Die ternäre Suche ist eine direkte Verallgemeinerung der binären Suche, die den aktuellen Bereich nicht in zwei, sondern in drei Teile teilt. Mit m1 = lo + ⌊(hi − lo) / 3⌋ und m2 = hi − ⌊(hi − lo) / 3⌋ vergleicht sie zwei Punkte pro Iteration. Liegt der Zielwert links von a[m1], geht die Suche im linken Drittel weiter; liegt er rechts von a[m2], im rechten Drittel; sonst im mittleren Drittel zwischen m1 und m2. Die Laufzeit ist O(log₃ n), also asymptotisch gleich der binären Suche. Allerdings macht die ternäre Suche pro Iteration zwei Vergleiche statt einem, weshalb sie in der Praxis langsamer ist als die binäre Suche; sie wird daher als reine Suche selten eingesetzt. Bekannt ist sie vor allem als Optimierungs-Werkzeug für unimodale (also strikt monoton steigende dann fallende) Funktionen.
Komplexität
- Best Case
O(1) - Average Case
O(log n) - Worst Case
O(log n) - Zusatz-Speicher
O(1)
Wann verwenden?
Klassische Anwendung: Maximum einer unimodalen Funktion finden, also einer Funktion, die zuerst steigt und dann fällt. Beispielsweise das Maximum einer Parabel oder die optimale Wurfweite eines Projektils. Als reine Suche in sortierten Arrays unterlegen der binären Suche.