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.
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.
