In Python, how do you find the index of the first value greater than a threshold in a sorted list?

In Python, how do you find the index of the first value greater than a threshold in a sorted list?

I can think of several ways of doing this (linear search, hand-written dichotomy,..), but I'm looking for a clean an reasonably efficient way of doing it. Since it's probably a pretty common problem, I'm sure experienced SOers can help!

Thanks!

Solution 1:

Have a look at bisect.

import bisect

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

bisect.bisect(l, 55) # returns 7

Compare it with linear search:

timeit bisect.bisect(l, 55)
# 375ns


timeit next((i for i,n in enumerate(l) if n > 55), len(l))
# 2.24us


timeit next((l.index(n) for n in l if n > 55), len(l))
# 1.93us

Solution 2:

You might get a better time than the enumerate/generator approach using itertools; I think itertools provides faster implementations of the underlying algorithms, for the performance mongers in all of us. But bisect may still be faster.

from itertools import islice, dropwhile

threshold = 5
seq = [1,4,6,9,11]
first_val = islice(dropwhile(lambda x: x<=threshold, seq),0,1)
result = seq.index(first_val)

I wonder about the difference between the bisect approach shown here and the one listed for your question in the doc examples, as far as idiom/speed. They show an approach for finding the value, but truncated to first line, it returns the index. I'd guess that since it's called "bisect_right" instead of "bisect," it probably only looks from one direction. Given that your list is sorted and you want greater-than, this might be the greatest search economy.

from bisect import bisect_right

def find_gt(a, x):
    'Find leftmost value(switching this to index) greater than x'
    return bisect_right(a, x)

Interesting question.