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

Question

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!

Answer 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 

Answer 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.