Suchalgorithmen
Lineare Suche, binäre Suche, Jump Search, Interpolationssuche und ternäre Suche mit lo/mid/hi-Zeigern auf einem sortierten Balken-Array.
- Lineare SucheLineare Suche interaktiv: vergleicht jeden Index der Reihe nach mit dem Zielwert. Funktioniert auf unsortierten Arrays und läuft im Worst Case in O(n).
- Binäre SucheBinäre Suche interaktiv: halbiert den Suchbereich an der Mitte und verschiebt lo oder hi. Braucht ein sortiertes Array und läuft in O(log n).
- Jump SearchJump Search interaktiv: springt in √n-Schritten durch ein sortiertes Array, dann linearer Block-Scan rückwärts. Sweet spot zwischen O(n) und O(log n).
- InterpolationssucheInterpolationssuche interaktiv: schätzt die Position des Zielwerts per linearer Interpolation. Bei gleichverteilten Werten sehr schnell, im Worst Case O(n).
- Ternäre SucheTernä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.
Vergleich der Verfahren
| Lineare Suche | O(1) | O(n) | O(n) | O(1) |
|---|---|---|---|---|
| Binäre Suche | O(1) | O(log n) | O(log n) | O(1) |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) |
| Interpolationssuche | O(1) | O(log log n) | O(n) | O(1) |
| Ternäre Suche | O(1) | O(log n) | O(log n) | O(1) |