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: Have a look at [bisect](http://docs.python.org/library/bisect.html).

    
    
    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
    

