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: jeder Index wird der Reihe nach mit dem Zielwert verglichen. Funktioniert auf unsortierten Arrays und Streams, läuft im Worst Case in O(n).
- Binäre SucheBinäre Suche interaktiv: Halbiert den Suchbereich anhand der Mitte und verschiebt lo oder hi. Voraussetzung sortiertes Array, läuft in O(log n) mit konstantem Zusatzspeicher.
- 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 extrem schnell, im Worst Case allerdings O(n).
- Ternäre SucheTernäre Suche interaktiv: teilt den Bereich an m1 und m2 in drei Drittel. O(log₃ n) und damit asymptotisch gleich wie die binäre Suche, klassische Anwendung sind unimodale Funktionen.