在 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)
是否可以做得更快或更好?谢谢。
请您参考如下方法:
由于您的列表已经排序,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"
