给定边界,找到间隔

Question

有这样的清单

[207, 357, 470, 497, 537]

其中每个数字表示一个区间的边界(0隐含在列表的开头),什么是pythonic方式找出给定数字n属于哪个区间？

所以间隔是

0: (0, 207)
1: (208, 357)
2: (358, 497)
3: (498, 537)

如果n=0,那么相应的间隔0,对n=360,它是2.

Answer 1

当然使用bisect模块:

>>> import bisect
>>> lst = [207, 357, 470, 497, 537]
>>> bisect.bisect_left(lst, 0)
0
>>> bisect.bisect_left(lst, 360)
2

该模块使用二进制搜索,这需要一个排序的序列.使用这样的序列,您可以通过在第一个和最后一个中间选择一个索引来将序列分成两半,以查看您需要的值是否为一半.然后继续划分所选的一半,直到找到匹配的插入点.这使得您可以在O(log N)时间内找到长度为N的序列的插入点,即非常快.