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

Question

假设我有一个经过排序的 float 列表。现在我想获取给定值的下一个较低项的索引。通常的 for 循环方法具有 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

bisect怎么样？ ？

>>> 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。