|
Diese stellt eine mögliche Verbesserung dar. Hier versucht man genauer zu erraten, wo sich das gesuchte Element befindet. Dies erinnert an die Suche in einem Telefonbuch, wo man eher vorne zu suchen beginnt, wenn der gesuchte Name mit einem B beginnt. Im Beispiel wird wieder nach der 13 gesucht:
Interpolationssuche erfordert für erfolgreiche aber auch für erfolglose Suche niemals mehr als lg[lg(N+1)] Vergleiche.
Die Interpolationssuche ist besonders für große, gleichmäßig verteilte Felder geeignet, da z.B. für eine Milliarde Elemente nur maximal 5 Schritte erforderlich wären. Ein Nachteil ist, daß die Interpolationssuche bei einer sehr ungleichmäßigen Verteilung hereingelegt werden kann. Bei kleinen Feldern ist auch der Vorteil, der durch die Interpolation entsteht, sehr gering.
|
