python - 有效地确定超出后续数字范围的数字是否在有序列表中。 (在 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

您可以 binary-search两次，对于范围的每个边界(使用 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