有效地确定后续数字范围中的数字是否在有序列表中.(在Python中)

Question

我们有一个有序的数字列表.现在我们要检查一系列数字的成员是否在列表中.

类似于range(5, 10) in mylist 如果5,6,7,8或9在mylist中它应该返回首先在列表中找到的元素,否则为Null或False.

例如,如果mylist类似于[1,2,3,7,8,10,15]函数将返回7.如果列表将是[1,2,3,4,12,13]函数将返回None/False.

现在想想大名单和大范围,操作变得无法实现.我该如何实现它以便它具有更好的性能？

Answer 1

对于范围的每个边界(使用),您可以二次搜索两次bisect.bisect_left().

如果返回的索引相同,则没有交集(返回None).

如果不是,则返回元素start_index(start_index您获取范围的索引start).

这是代码:

import bisect
def intersect_range(lst, start, stop):
     start_i = bisect.bisect_left(lst, start)
     stop_i = bisect.bisect_left(lst, stop)
     if start_i == stop_i:
         return None
     else:
         return lst[start_i]

intersect_range([1,2,3,7,8,10,15], 5, 10)
=> 7
intersect_range([1,2,3,7,8,10,15], 5, 6)
=> None
intersect_range([1,2,3,7,8,10,15], 15,30)
=> 15
intersect_range([1,2,3,7,8,10,15], 0,1) # "stop" is excluded from range
=> None

由于您执行了两次二进制搜索,因此复杂度为O(logN),其中N是列表的长度.

编辑:

还有一个稍快的选择,即二进制搜索范围的开始,然后检查是否lst[start_index]在范围(start <= lst[start_i] < stop).这将logN操作次数从两个减少到一个.代码如下所示:

def intersect_range(lst, start, stop):
    start_i = bisect.bisect_left(lst, start)
    if start <= lst[start_i] < stop:
        return lst[start_i]
    else:
        return None