如何在有序列表中更高效查找指定数值的前驱元素索引？

你当前用的遍历方法时间复杂度是O(n)，当列表元素数量多的时候，效率会明显下降。因为列表是有序的，二分查找才是最高效的方案，时间复杂度能降到O(logn)，数据量越大，提速效果越显著。

Python标准库自带的bisect模块专门用来处理有序序列的二分查找操作，用它来实现前驱元素查找非常方便：

实现代码 #

import bisect

x_list = [1, 3.5, 5, 9.2, 20, 50.75]
n = 7.5

# 找到n应该插入的位置（保持列表有序的插入点）
insert_pos = bisect.bisect_left(x_list, n)
# 前驱元素的索引就是插入位置减1
xlow = insert_pos - 1
print(xlow)  # 输出2，和示例结果一致

原理说明 #

bisect.bisect_left会返回第一个大于等于n的元素的索引，所以这个位置的前一个元素就是最后一个小于n的元素（也就是n的前驱）。

边界情况处理 #

如果n比列表中所有元素都小，insert_pos会是0，此时xlow会变成-1，你可以根据需求做特殊处理：

if insert_pos == 0:
    print("不存在前驱元素")
else:
    xlow = insert_pos - 1
    print(xlow)

对比遍历方法，当列表有10000个元素时，遍历最坏要走10000次循环，而二分查找只需要约14次计算，效率提升非常明显。

内容的提问来源于stack exchange，提问作者darren