Python: Efficient lookup by interval

Question

I have a large lookup table where the key is an interval:

| min | max | value   |
|-----|-----|---------|
| 0   | 3   | "Hello" |
| 4   | 5   | "World" |
| 6   | 6   | "!"     |
| ... | ... | ...     |

The goal is to create a lookup structure my_lookup that returns a value for each integer, depending on the range the integer is in. For example: 2 -> "Hello", 3 -> "Hello", 4 -> "World".

Here is an implementation that does what I want:

d = {
  (0, 3): "Hello",
  (4, 5): "World",
  (6, 6): "!"
}

def my_lookup(i: int) -> str:
  for key, value in d.items():
    if key[0] <= i <= key[1]:
      return value

But looping over all entries seems inefficient (the actual lookup table contains 400.000 lines). Is there a faster way?

Answer 1

If your intervals are sorted (in ascending order), you can use bisect module (doc). The search is O(log n) instead of O(n):

min_lst = [0,       4,       6]
max_lst = [3,       5,       6]
values = ['Hello', 'World', '!']

import bisect

val = 2

idx = bisect.bisect_left(max_lst, val)
if idx < len(max_lst) and min_lst[idx] <= val <= max_lst[idx]:
    print('Value found ->', values[idx])
else:
    print('Value not found')

Prints:

Value found -> Hello