Was ist ein Beispiel für eine Interpolationssuche, die langsamer ist als die binäre Suche?

Question

Ich verstehe, dass Interpolation Suche nicht nur eine sortierte Liste erfordert, sondern auch gleichmäßig verteilt. Ich suche nach einer verständlichen Situation, in der die Interpolationssuche langsamer ist als die binäre Suche.

Danke

Answer 1

Wenn wir gleichmäßige Verteilung der Werte annehmen, so dass wir einfache lineare Interpolation verwenden werden. Also, wenn die Werte sind: 1,2,3,4,5,6,7,8,9,10000000 Und wir suchen nach Nummer 9, Suche mit linearer Interpolation wird durch alle gehen (mit Ausnahme der ersten und letzten) die Indizes vor dem Finden der richtigen. In solchen Fällen ist die Interpolationssuche O (n).