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!
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
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)