Given boundaries, find interval

Question

Having a list like this

[207, 357, 470, 497, 537]

where each number denotes the boundary of an interval (0 being implicit at the beginning of the list), what is a pythonic way of finding out to which interval a given number n belongs to?

So the intervals are

0: (0, 207)
1: (208, 357)
2: (358, 497)
3: (498, 537)

If n=0, then the corresponding interval is 0, for n=360, it's 2.

Answer 1

Using the bisect module of course:

>>> import bisect
>>> lst = [207, 357, 470, 497, 537]
>>> bisect.bisect_left(lst, 0)
0
>>> bisect.bisect_left(lst, 360)
2

The module uses binary search, which requires a sorted sequence. With such a sequence you can divide the sequence in half by picking an index mid-way between the first and last, to see if the value you need is in either half. You then continue dividing the selected half until you found a matching insertion point. That lets you find the insertion point in O(log N) time for a sequence of length N, i.e. very fast.

Answer 2

Using numpy and np.searchsorted:

import numpy as np

boundaries = [207, 357, 497, 537]
values = [0, 207, 300, 500, 9999]

np.searchsorted(intervals, values)

This gives:

>>> array([0, 0, 1, 3, 4])

(if the value 207 was instead intended to belong to the interval 1 , side='right' could be used)