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

Question

假设我有一个已经排好序的浮点数列表。现在我想找到一个给定值的下一个较小的元素的索引。通常用循环的方法复杂度是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模块。这个函数

bisect.bisect_left(mylist, compareValue)

会返回一个合适的位置，让你可以把某个项目放进列表中，同时保持列表的排序状态。

Answer 2

你可以在一个数组或列表上进行二分查找，这样可以找到你想要的对象的索引位置。如果你想找到它下面的那个元素的索引，也可以通过这个方法来实现（前提是确实存在一个比它小的元素！）。

参考链接：Python中的二分查找（分割查找）

在比较浮点数是否相等时要小心哦！

Answer 3

那bisect怎么样呢？你可以在这里查看它的文档：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来处理。