python - 在 Python 中，如何找到排序列表中第一个大于阈值的值的索引？

Question

在 Python 中，如何找到排序列表中第一个大于阈值的值的索引？

我可以想到几种方法（线性搜索，手写二分法，..），但我正在寻找一种干净且合理有效的方法。由于这可能是一个很常见的问题，我相信有经验的 SOers 可以提供帮助！

谢谢！

Answer 1

看看bisect。

import bisect

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

bisect.bisect(l, 55) # returns 7

将其与线性搜索进行比较：

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

Answer 2

您可能会比使用 itertools 的枚举/生成器方法获得更好的时间；我认为 itertools 为我们所有人的性能贩子提供了更快的底层算法实现。但是 bisect 可能仍然更快。

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)

我想知道这里显示的二等分方法与文档示例中为您的问题列出的方法之间的区别，就成语/速度而言。他们展示了一种查找值的方法，但截断到第一行，它返回索引。我猜想因为它被称为“bisect_right”而不是“bisect”，所以它可能只从一个方向看。鉴于您的列表已排序并且您想要大于，这可能是最大的搜索经济。

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)

有趣的问题。

Answer 3

最后一个元素的相关索引和值大于阈值

l = [1, 4, 9, 16, 25, 36, 49, 64, 100, 81, 100]
max((x,i) for i, x in enumerate(l) if x > 4)
(100, 10)