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

由于您的列表已经排序，因此平分模块是您的朋友。它将为您执行 O（log（n）） 搜索。例如，bisect_right和bisect_left的功能很方便。如果 bisect_right 返回奇数，则 you number 在一个范围内，该范围的开头是返回值减去 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"

Answer 2

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

Answer 3

这可能不是更快，但这里有一个可能的解决方案（特别是如果您需要避免每次创建 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 解决方案对该解决方案进行基准测试，看看您是否获得/失去任何收益。

祝你好运！

Answer 4

你可以使用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)

它假定该值位于第一个和最后一个元素中。