蟒，找到其中多个属于一个范围，范围是从整数

有整数列表，列表中的每个连续的整数形成了一个范围。对于给定的数字，我想查找数字所属的范围，并返回范围（或范围的起点）。例如。

名单：

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

数量：

结果：

(99,12) OR 99

的数字是按升序排列，并形成区域不重叠，大小的列表总是2的倍数。

该列表可能很长，并且有很多数字需要检查。

我试图整数包成intervalTree，并使用搜索（）函数来检查，但它似乎慢：

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

t.search(theNumber)

是否有可能做的更快，更好？谢谢。

来源

2016-02-19 Xiangwu

由于您的清单已经排序，bisect module是你的朋友。它会为你做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"

来源

2016-02-19 18:23:22 innoSPG

非常感谢，它运作良好。 – Xiangwu

不客气@祥武。我很高兴这是有帮助的 – innoSPG

您可以使用二进制搜索的修改来提高平均时间复杂度。 1）首先将给定的数字与列表的中间元素进行比较。如果它比右半部分的中间大，则将其与左半部分的中间比较。 2）继续第一步，直到你得到数字所在的区间。

来源

2016-02-19 18:14:02 Rndomcoder

这可能不会更快，但这里有一个可能的解决方案（尤其是如果您需要避免每次创建IntervalTree的开销）。

def find_range(num, the_list): 
    midpt = len(the_list)/2 
    left_list = the_list[0:midpt] 
    right_list = the_list[midpt:] 
    if num >= left_list[midpt - 1] and num <= right_list[0]: 
     rv = (left_list[midpt - 1], right_list[0]) 
    elif num < left_list[midpt - 1]: 
     rv = find_range(num, left_list) 
    else: 
     rv = find_range(num, right_list) 
    return rv

我有一个小样本测试它，和它的作品如预期，但我想基准对IntervalTree解决方案这种方式，看看你获得/损失什么。

祝你好运！

来源

2016-02-19 18:22:25 FriendlyNeighborhoodBonehead

你可以使用Python的bisect库如下：

import bisect 

loi = [1, 8, 11, 20, 37, 66, 99, 120, 56000, 59001] 
index = bisect.bisect_left(loi, 100) 

print "({},{})".format(loi[index-1], loi[index])

这将显示如下输出：

(99,120)

它假定值是第一个和最后一个元素中。

来源

2016-02-19 18:24:09

蟒，找到其中多个属于一个范围，范围是从整数

回答

相关问题