4 ms·
Interpolation searches are a bit tricky in practice. As the author notes, if the keys are uniformly distributed, it can work well. But if you're given a set o
by j_baker 16y ago
Interpolation searches are a bit tricky in practice. As the author notes, if the keys are uniformly distributed, it can work well. But if you're given a set of values that aren't uniformly distributed, it can be much slower than a binary search.
- kenjackson 16y agoFrom what I read it doesn't require a uniform distribution. The author says to model the key distribution, so if its uniform you guess based on a uniform distribution. If it's normal then you use normal, etc... Of course this presumes you know the distribution of keys. In many cases I don't think people know the distribution of keys, or even the values of the extremas.