摘要 : A new dynamic Interpolation Search (IS) data structure is presented that achieves O(log log n) search time with high probability on unknown continuous or even discrete input distributions with measurable probability of element col... 展开 A new dynamic Interpolation Search (IS) data structure is presented that achieves O(log log n) search time with high probability on unknown continuous or even discrete input distributions with measurable probability of element collisions, including power law and Binomial distributions. No such previous result holds for IS when the probability of element collisions is measurable. Moreover, our data structure exhibits O(1) search time with high probability (w.h.p.) for a wide class of input distributions that contains all those for which o (log log n) expected search time was previously known. 收起