python，找到一个数字所属的范围，范围由整数列表组成

Question

在 python 中，

有一个整数列表，列表中的每个连续整数组成一个范围。对于给定的数字，我想找到数字所属的范围，并返回范围(或范围的开始)。例如

列表:

[1, 8,   11, 20,   37, 66,   99, 120, ...... ,56000,59001, .....]

人数:

100

结果:

(99,12) OR 99 

数字递增，形成的区域不重叠，列表的大小总是2的倍数。

列表可能很长，需要检查的数字很多。

我试图将整数打包成一个intervalTree，并使用search()函数进行检查，但它看起来很慢:

for i in integerList:
    t = IntervalTree(Interval(*iv) for iv in zip(*[iter(annotation_dict.get(i))] * 2))

t.search(theNumber)

是否可以做得更快或更好？谢谢。

Answer 1

由于您的列表已经排序，bisect module是你的 friend 。它将为您执行 O(log(n)) 搜索。例如函数 bisect_right 和 bisect_left 就很方便。如果 bisect_right 返回一个奇数，那么您的数字在一个范围内，并且该范围的开头是返回值减去 1。如果它是偶数，那么你的数字在你列表的两个不同范围之间。看下面的示例代码，我直接把结果减一，所以我测试的和解释的是相反的。

import bisect
loi = [1, 8, 11, 20, 37, 66, 99, 120, 56000, 59001]
idx = bisect.bisect_right(loi,100)-1

if idx%2 == 0:
    print loi[idx]
else:
    print "not in a range"