Skip to main content
 首页 » 编程设计

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

2025年05月04日9Terrylee

在 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"