给定一个排序列表，找到数字的索引

Question

给定一个sorted list和一个数字n，以最有效(最快(的方式在列表中查找位于n之前的索引。

排序列表示例：

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

编号n，例如n=7.5

示例答案：列表中n之前的值的索引为2。

这就是我迄今为止所尝试的：

x_list = [1, 3.5, 5, 9.2, 20, 50.75]
n = 7.5
for i, v in enumerate(x_list):
if v < n: xlow = i
else: break
print(xlow)

我能比上面的方法更快地找到吗？

注：这个列表是sorted，而其他性质相同的问题是unsorted。

Answer 1

您可以使用bisect执行二进制搜索：

import bisect
n = 7.5
index = bisect.bisect_left(x_list, n)-1

输出：2

注意。如果目标位于第一个索引之前，则会返回-1，如果需要，可以避免使用max(0, bisect.bisect_left(x_list, n)-1)