Mapping with continguous ranges of keys

[Thomas Nyberg]

On 12/15/2016 09:06 AM, Steve D'Aprano wrote:
> Has anyone dealt with data like this and could give a recommendation of the
> right data structure to use?
>

I haven't dealt with a data structure exactly like this, but it's 
basically a sparse array. (I'm sure it has a name somewhere in the 
academic literature, but I couldn't find it with a quick search right 
now...)

My solution to what you're asking for would be to have a list of 
key-value pairs, only adding a key to the list if it "changes" the 
value. I.e. your data structure would be this:

l = [
     (1, "foo"),
     (101, "bar"),
     (103, "foobar"),
     (104, "bar"),
     (105, "foo"),
]

Then the only thing you need to do is define the lookup function. I 
would basically just do a binary search on the first values in the 
tuples. I.e. if "n" is your integer, you check if the middle values of 
the list l has it's first element as less than or greater than your 
value. Then you split l in two and do the same thing. Do this until you 
either find your value, or you find a value less than your value with 
the added property that the next value is greater than your value. After 
that you spit out the final second value.

There might be better ways to find the keys, but I think this approach 
is probably your best bet.

Cheers,
Thomas