在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

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

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)