Find value within a range in lookup table

Question

I have the simplest problem to implement, but so far I have not been able to get my head around a solution in Python.

I have built a table that looks similar to this one:

501 - ASIA
1262 - EUROPE
3389 - LATAM
5409 - US

I will test a certain value to see if it falls within these ranges, 389 -> ASIA, 1300 -> LATAM, 5400 -> US. A value greater than 5409 should not return a lookup value.

I normally have a one to one match, and would implement a dictionary for the lookup.

But in this case I have to consider these ranges, and I am not seeing my way out of the problem.

Maybe without providing the whole solution, could you provide some comments that would help me look in the right direction?

It is very similar to a vlookup in a spreadsheet.

I would describe my Python knowledge as somewhere in between basic to intermediate.

Many thanks in advance.

Answer 1

You could use the bisect module. Instead of linear search, that would use binary search, which would hopefully be faster:

import bisect

places = [
    (501, 'ASIA'),
    (1262, 'EUROPE'),
    (3389, 'LATAM'),
    (5409, 'US'),
]
places.sort() # list must be sorted

for to_find in (389, 1300, 5400):
    pos = bisect.bisect_right(places, (to_find,))
    print '%s -> %s' % (to_find, places[pos])

Will print:

389 -> (501, 'ASIA')
1300 -> (3389, 'LATAM')
5400 -> (5409, 'US')

Answer 2

First make a sorted index:

index = sorted(table.iteritems())

Then, use bisect to find your key:

_, value = bisect.bisect_left(index, (key, ''))

Answer 3

If you just have 5409 values I would just put each interger in the range in the dictonary and do normal lookups. Each entry takes 12bytes, the total is just 500Kb, so why bother.

Here is some neat code to do this:

places = [
    (501, 'ASIA'),
    (1262, 'EUROPE'),
    (3389, 'LATAM'),
    (5409, 'US'),
]

def make_zones( borders ):
    last = 0
    for n,v in borders:
        for i in range(last, n+1):
            yield i,v
        last = i+1

zones = dict(make_zones(places))

print zones[501], zones[502]