Find a value within a range in a lookup table

Question

I have the easiest problem to implement, but so far I have not been able to find a solution in Python.

I built a table that looks like this:

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

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

Usually I have a one-to-one match and implement a search dictionary.

But in this case, I must consider these ranges, and I do not see my way out of the problem.

Perhaps without providing the whole solution, could you give some comments that will help me to look in the right direction?

It is very similar to a vlookup in a spreadsheet.

I would describe my knowledge of Python as somewhere between basic and intermediate.

Answer 1

You can use the bisect module. Instead of a linear search that will use a binary search, which I hope will 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]) 

It will be printed:

 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 have only 5,409 values, I would just put each integer in a dictionary and do a normal search. Each record takes 12 bytes, the total number is only 500Kb , so why bother.

Here are a few options:

 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] 

Answer 4

 places = [(501,"ASIA"),(1262,"EUROPE"),(3389,"LATAM"),(5409,"US")] places.sort() def getSection(places,requests): PL= len(places) LAST=places[-1][0] for R in requests: for P in range(PL): if not (R < 0 or R>LAST):#keep away integers out of range if R<=places[P][0]: print R,"->",places[P][1] break else: break 

Call getSection,

 getSection(places,(5000000,389,1300,5400,-1,6000)) 

gives:

 389 -> ASIA 1300 -> LATAM 5400 -> US