Interpolationssuche
Schätzt die Position des Zielwerts über lineare Interpolation, fast wie ein Lineal anlegen.
- Vergleiche 0
- Ergebnis noch offen
- Vergleich
- Tausch
- sortiert
Pseudocode
1 lo = 0; hi = n - 1
2 while lo <= hi and a[lo] <= target <= a[hi]
3 pos = lo + ((target - a[lo]) * (hi - lo)) / (a[hi] - a[lo])
4 if a[pos] == target: return pos
5 if a[pos] < target: lo = pos + 1
6 else: hi = pos - 1
7 return -1
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Die Interpolationssuche ist eine Erweiterung der binären Suche, die nicht stur die Mitte des aktuellen Bereichs nimmt, sondern den vermuteten Index des Zielwerts via linearer Interpolation berechnet. Aus dem aktuellen Wertebereich a[lo] bis a[hi] und dem Zielwert ergibt sich pos = lo + ((target − a[lo]) · (hi − lo)) / (a[hi] − a[lo]). Bei gleichmäßig verteilten Daten landet diese Schätzung sehr nahe am Treffer und der Bereich schrumpft schneller als nur halbiert. Damit liegt die Laufzeit bei gleichverteilten Daten bei O(log log n) im Average Case, fast unschlagbar schnell. Im Worst Case (etwa stark ungleich verteilte Werte oder geometrisch wachsende Zahlen) degeneriert sie aber auf O(n). Voraussetzung sind ein sortiertes Array und gleichverteilte Werte; bei nicht-numerischen oder ungleichmäßigen Daten ist die binäre Suche vorzuziehen.
Komplexität
- Best Case
O(1) - Average Case
O(log log n) - Worst Case
O(n) - Zusatz-Speicher
O(1)
Wann verwenden?
Optimal bei großen, sortierten Datensätzen mit gleichmäßig verteilten Werten, etwa numerischen Indizes oder ID-Spalten ohne Lücken. Bei realen Daten oft riskant, weil die O(log log n)-Garantie schnell auf O(n) kippt; klassische Anwendung sind algorithmische Optimierungen in Wettbewerbsprogrammierung.