[DrJokepu]

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.

[sesqu]

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.

[by]

We only need a ball-park estimate of the distance between keys not an exact measurement. Anything better than random should be an improvement.