对于范围的每个边界,您可以使用

binary-search两次(使用

bisect.bisect_left()).

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

如果不是,则返回start_index处的元素(其中start_index是您的范围开始时获得的索引).

这是代码：

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