在排序列表中查找下一个较低的项目

Question

假设我有一个Floats排序列表.现在我想获得给定值的下一个较低项的索引.通常的for-loop aprroach具有O(n)的复杂性.由于列表已排序,因此必须有一种方法可以使用O(log n)获取索引.

我的O(n)方法:

index=0
for i,value in enumerate(mylist):
    if value>compareValue:
        index=i-1

在O(log n)中是否有解决该问题的数据类型？

最好的问候塞巴斯蒂安

Answer 1

平分怎么样？

>>> import bisect
>>> float_list = [1.0, 1.3, 2.3, 4.5]
>>> i = bisect.bisect_left(float_list, 2.5)
>>> index = i - 1
>>> index
2

您可能必须单独处理搜索值小于或等于列表中最低/最左侧值的index == -1情况(在本例中).

根据您在平等的情况下希望拥有的索引,您可能必须使用bisect_right.

Answer 2

您可以对数组/列表执行二进制搜索以获取您正在查找的对象的索引,并获取其下方的索引以获取较低的条目(假设实际上存在较低的条目!).

请参阅:Python中的二进制搜索(二分)

比较浮点数时要小心相等!