Is there a faster way to check if a number is within an interval?

Question

I have a list of intervals that I have been sorting like this:

intervals=['132-237','156-223','589-605',...]

I then get a number and want to determine which intervals it is included in:

number=160 #number gotten
for lines in intervals:
    lines=line.split(sep='-')
    if number>=int(lines[0]) and number<=int(lines[1]):
        record=record+1 #actually recording it more complicated

is there a way to do this without a for loop?

Apply http://stackoverflow.com/questions/4446112/search-for-interval-overlap-in-list-of-intervals with a one point interval `[a,b] = [number, number] — hivert, Feb 05 '14 at 20:22
Any reason you can't use a for loop? If speed is the concern because you have a gigantic list of intervals, I don't think python is your answer. — Chris Arena, Feb 05 '14 at 20:28
@Decency Using a loop is an O(n) algorithm. An appropriate data structure would allow O(lg n) lookups - a substantial improvement regardless of the language involved. — chepner, Feb 05 '14 at 20:30

Hyperboreus · Accepted Answer · 2014-02-05T20:35:02.567

3

You could use a list of tuples.

intervals = [(132,237),(156,223),(589,605)]
number = 160
for start, stop in intervals:
    if start <= number <= stop:
        print (start, stop)

As you asked explicitly for a solution without a for-loop, please look at Markku K's comment to this answer.

If you want to avoid for at all, I fear the way to go is recursion for which python is not cut out.

edited Feb 05 '14 at 20:35

answered Feb 05 '14 at 20:16

Hyperboreus

31,997
9
47
87

Since the OP asked for a solution without a 'for loop', you could use a list comprehension instead: `[tup for tup in intervals if tup[0] <= number <= tup[1]]`. – Markku K. Feb 05 '14 at 20:33
@MarkkuK. Thank you I overlooked that part. Although I don't know which is the advantage of a `for` in a list comprehension, compared to an explicit `for`-loop. I will update my answer. – Hyperboreus Feb 05 '14 at 20:34
Right, it really isn't a big difference. I initially posted that suggestion as a separate answer, but decided the change was so insignificant, that I would just write a comment instead. – Markku K. Feb 05 '14 at 20:35
+1 for not parsing strings. And yes, a list comprehension is a solution - a loop not visible to coder - but it is not faster in this case – cox Feb 05 '14 at 20:40

score 1 · Answer 2 · answered Feb 05 '14 at 20:16

intervals = ['132-237','156-223','589-605']
intervals = [tuple(map(int, i.split('-'))) for i in intervals]
number = 160
for low,high in intervals:
    if low <= number <= high:
        print(number, "is between", low, "and", high)
        break

Of course, a binary search would be faster:

intervals = ['132-237','156-223','589-605']
intervals = [tuple(map(int, i.split('-'))) for i in intervals]
def binSearch(number, intervals):
    intervals.sort()
    mid = len(intervals)//2  # a//b is in python3. Use len(intervals)/2 for python2
    low,high = intervals[mid]
    if number > high:
        return binSearch(number, intervals[mid+1:])
    elif number < low:
        return binSearch(number, intervals[:mid])
    elif low <= number <= high:
        return (low,high)
    else:
        return "no appropriate interval exists"

`//` works the same in Python 2.2 and later as it does in Python 3. It's `/` that works differently in Python 3 than it did in Python 2. — chepner, Feb 05 '14 at 20:33

score 1 · Answer 3 · answered Feb 05 '14 at 20:22

Here's my solution:

def inside_interval(num, interval):
    start, end = interval.split(sep='-')
    return num in range(int(start), int(end))

And some sample output:

intervals = ['132-237', '156-223', '589-605']
print(inside_interval(150, intervals[0]))
print(inside_interval(123, intervals[1]))
print(inside_interval(600, intervals[2]))
# True, False, True

Here's using the example with a for loop (in a list comprehension). You could use another construct here if you really wanted to, but you'd need a good reason to do so.

num = 160
intervals_list = [inside_interval(num, interval) for interval in intervals]
# intervals_list = [True, True, False]

This gets you an output of Booleans that correspond to your list of intervals.

I'd personally suggest that you turn your intervals into a more useful format, rather than using strings. That will make it easier to do other comparisons.

Is there a faster way to check if a number is within an interval?

3 Answers3