计算排序列表中截止值小于(大于)的元素数量的有效方法

Question

假设我们有一个排序列表:

lst = [1,3,4,89,456,543] # a long one

我们想要做的是找到列表中小于的元素数量mx.

简单:

n = len([x for x in lst if x < mx])

或与发电机:

n = sum(1 for x in lst if x < mx)

我假设第二种方法应该稍快一点,但是,这里的问题是我们在早期停止时会查看列表的所有元素.它不使用列表已排序的事实.

是的,我可以用循环来做到这一点:

s = 0
for x in lst:
    if x >= mx:
        break
    s += 1

但是,我觉得必须有一个更好(更短和/或更快)的方法来做同样的事情,可能有一些发电机或外部模块功能？

Answer 1

我们可以通过二进制搜索做得更好,这可以在bisect模块中轻松实现:

import bisect
n = bisect.bisect_left(lst, mx)

这需要时间长度为对数lst,而早期终止的线性搜索是线性的n.这通常会更快.

如果要使用线性搜索,takewhile函数from itertools可以提前停止迭代:

import itertools
n = sum(1 for _ in itertools.takewhile(lambda x: x < mx, lst))