# Ternäre Suche visualisieren: drei Drittel statt zwei Hälften

> Ternäre Suche interaktiv: teilt den Bereich an m1 und m2 in drei Teile. O(log₃ n), asymptotisch wie die binäre Suche, typisch für unimodale Funktionen.

Adresse: https://marckimmel.de/informatik/suchalgorithmen/ternaere-suche
English version: https://marckimmel.de/en/informatik/suchalgorithmen/ternaere-suche.md

Teilt den Suchbereich in drei Drittel und vergleicht an zwei Drittel-Punkten.

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.

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.

## Weiter

- [Suchalgorithmen](https://marckimmel.de/informatik/suchalgorithmen.md)