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!

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

Interesting question.

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow