Constant Time Membership Indexing for Intervals on the Real Line?

Say I were given a set of weights adding up to 开发者_开发技巧1, and I lined them up one after another to make a series of bins with length proportional to their weight. I assign each bin an integer corresponding to its place in line.

Given any number in [0,1], I would like to be able to check which index corresponds to the bin this number lands in. Can I come up with an algorithm to do this in constant time?

A logarithmic time solution is straightforward, but I'm hoping for one better!

This can probably be accomplished using the alias method, which can be used to generate random samples from a discrete distribution in time O(1). I believe that you can adapt this algorithm to solve your problem by simply inverting the transform so that instead of mapping from a uniform random variable to a discrete bucket, you map from a discrete bucket to a uniform variable. From there, you can determine which bucket the value falls in.

Hope this helps!

EDIT: I recently wrote an extensive write-up of the alias method and other related tricks. Hopefully this makes the algorithm and its intuition clearer and easier!

Create a table with k entries and 1/k must be smaller than your smallest entry. Then you fill the table with entries to where they point to, and then you have O(1).

If you relax the restraint on k, you can create a multistaged lookup, where the first step is as above, but the second step is a linear or logarithmic search. This then becomes a O(log2(n/k)). n/k, k=n => O(log2(1)) = O(1) ?

To find which entry in the table to use, it is floor(x*k)