python - 找到最大数字 <= 其他数字

Question

我有一个L包含排序数字的列表。

我有一个号码x，随意。我希望从中找到最大的L数字<= x。我可以用一个循环来做到这一点，但很好奇是否有一个 Pythonic 单行或花哨的函数。

Answer 1

使用bisect模块。这种方法的复杂性O(LogN)与一个简单的循环相比O(N)。

>>> import bisect
def solve(lis, item):
     ind = bisect.bisect_right(lis, item, hi = len(lis)-1)
     return lis[ind] if lis[ind] <= item else lis[ind-1]

>>> L = range(10, 100)
>>> L.remove(15)       
>>> solve(L,15)
14
>>> solve(L,17)
17
>>> L.pop(20)
31
>>> solve(L,31)
30

Answer 2

最快的方法是使用bisect.bisect_left：

>>> r = range(300)
>>> import bisect
>>> r[bisect.bisect_left(r,280)]
280

这导致算法需要 O(log(N)) 次操作（平均），而直接循环平均需要 O(N) 次操作。

为了避免出现IndexError在范围的顶端，您可以设置hi关键字：

>>> r[bisect.bisect_right(r,320,hi=len(r)-1)]
299

Answer 3

>>> max([x for x in [1,3,5,7,9] if x <= 5])
5

Answer 4

我看到一个受函数式编程启发的答案，但它被删除了，所以我将发布类似的内容：

>>> import functools
>>> L = [1, 3, 15]
>>> x = 10
>>> functools.reduce(lambda a,b: a if b > x else max(a,b), L)
>>> 3

请注意，bisect其他人显示的解决方案在排序列表上更有效，但是如果列表未排序，这与正常for循环一样有效（或与dav 的解决方案一样有效），因为复杂度为 O(n)。

这个例子只是为了展示python中的一些函数式编程概念。