I agree. It does not depend on key distribution. Nor on the type of the key. But we do need to be able to estimate this

    (key - min) / (max - min)

where the variables are all keys and we want the expression to give a number between 0 and 1. We just need some way of estimating the 'distance' between keys for the subtraction to work. It does not need to be an exact distance, an average estimate better than random should beat the binary search.

The algorithm they give is effectively a linear interpolation. We could beat their algorithm by fitting a curve to the accumulated known points rather than a straight line to the nearest two points.