O(1) access into an array-like data structure with numerical ranges for keys Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies...

Summary: I have a data structure with probability ranges assigned to the elements, and I want to "roll the dice" and get the element at that spot. I'm wondering if there's a (good) way to do this in O(1) time?

Assume I've got a data structure like this, where the indices/keys represent ranges, and the values are what I want:

a = {
  [0..0.3) -&gt; "foo",
  [0.3..0.4) -&gt; "bar",
  [0.4..0.9) -&gt; "baz",
  [0.9..1.0] -&gt; "qux"
}


I want to retrieve a value from that array using a randomly generated number between 0 and 1. So, using that previous example, I do something like:

a[0.2] == "foo"
a[0.3] == "bar"
a[0.5565] == "baz"
a[0.8] == "baz"
...and so forth


I think I could store the data in a tree structure where I could walk to the correct element in O(log(n)) time, but I'm wondering if there's a clever way to do it in O(1) time.

I'm also curious if there is a specific name for this kind of data structure. It seems like someone would have played with this at some point.

As background, I'm toying with creating a Markov generator, and that requires storing the frequencies for all the words/token pairs. I'm guessing this is a solved problem already, and there are probably better solutions than what I'm proposing, but it seemed like an interesting problem and now I'm curious about the index-by-range problem all by itself, independent of the Markov aspect.
Perhaps what you're looking for is a Direct-adress Table

You can set up the keys as the ranges you've provided. Since the set of keys is quite small (4 intervals), a Direct-adress Table is a simple solution to your problem. It has the advantage of retrieving data in O(1)

The keys would hold a pointer to the data you want to retrieve.

For example, you can set a variable key1 as the interval [0..0.3). 
We generate a random number x, and get 0.1.
Since 0.1 meets the conditions of the first key ( x >= 0 and x &lt; 0.3), we can retrieve the data stored in key1 in O(1) time.

If you want more information about a Direct-adress Table or O(1) operations on dictionaries, I recommend Introduction to Algorithms, 3rd Edition, Chapter 11