News for hackers. Stuff that matters.
Re:Beating Binary Search by DrJokepu on Thursday June 17, 2010 @08:53AM (#1438691)
It doesn't need to be an integer but you're right in that it requires an additional property of the key type that most sorting and searching algorithms do not need: being able to measure the distance between two keys. Most algorithms only need to be able to decide whether a key is less, equal or greater than another key.
Re:Beating Binary Search by sesqu on Friday June 18, 2010 @03:25PM (#1443342)
This is implicit in having access to the (cumulative) key distribution. Still, the interpolation function can turn out to be pretty expensive, if your data isn't uniform 0-100.
Re:Beating Binary Search by by on Thursday June 17, 2010 @09:22AM (#1438784)
We only need a ball-park estimate of the distance between keys not an exact measurement. Anything better than random should be an improvement.