高效查找有序列表中元素的索引

Question

我有一个已经排好序的列表 l（大约有20,000个元素），我想找到列表中第一个超过给定值 t_min 的元素。目前，我的代码是这样的。

def find_index(l):   
    first=next((t for t in l if t>t_min), None) 
    if first==None:
        return None
    else:
        return l.index(first)

为了测试代码的性能，我使用了 cProfile 来运行一个测试循环，并通过与一个控制循环比较，去掉了随机生成列表所需的时间：

import numpy
import cProfile

def test_loop(n):
    for _ in range(n):
        test_l=sorted(numpy.random.random_sample(20000))
        find_index(test_l, 0.5)

def control_loop(n):
    for _ in range(n):
        test_l=sorted(numpy.random.random_sample(20000))

# cProfile.run('test_loop(1000)') takes 10.810 seconds
# cProfile.run('control_loop(1000)') takes 9.650 seconds

每次调用 find_index 函数大约需要 1.16 毫秒。考虑到我们知道列表是排好序的，有没有办法让代码更高效呢？

Answer 1

标准库中的 bisect 模块在这方面非常有用，文档里有一个示例，正好说明了这个用法。

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError