5 ms·
Beating Binary Search
- panic 16y agoSee earlier discussion at http://news.ycombinator.com/item?id=1438299 http://news.ycombinator.com/item?id=1438299
- j_baker 16y agoInterpolation 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.
- 16s 16y agoWe recently switched a C++ application from using a sorted std::vector and std::binary_search to using boost::unordered_set. The performance improvement on large sets (millions) was dramatic. unordered_set really does average O(1) time complexity. However, it was slightly slower than binary_search on smaller sets, but not so much slower to matter.