algorithm - 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