大尺寸布尔序列真值区间的O(logn)高效算法问询

当序列中仅存在单个连续真值区间时，完全可以通过两次二分查找在O(logn)时间复杂度内定位区间的左右边界，完美适配10亿级规模的序列。

核心思路 #

因为真值区间是连续且唯一的，我们可以拆分问题为两个独立的二分查找：

1. 左边界查找：在整个范围内找到最小的索引idx，使得fn(idx)返回True
2. 右边界查找：以左边界为起点，找到最大的索引idx，使得fn(idx)返回True

每次二分查找会将搜索范围减半，对于10亿规模的序列，单次二分最多需要约30次fn调用（log2(1e9)≈30），两次总计约60次调用，按每次fn耗时0.5秒计算，总耗时仅30秒左右，完全满足高效需求。

实现代码 #

def fn(idx):
    # 实际逻辑耗时0.5秒，此处为示例逻辑
    return 500000000 <= idx <= 700000000

def find_left_bound(fn, a, b):
    """查找最小的满足fn(idx)为True的索引"""
    left, right = a, b
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if fn(mid):
            result = mid
            right = mid - 1  # 向左收缩，尝试找到更小的符合条件的索引
        else:
            left = mid + 1
    return result

def find_right_bound(fn, a, b):
    """查找最大的满足fn(idx)为True的索引"""
    left, right = a, b
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if fn(mid):
            result = mid
            left = mid + 1  # 向右收缩，尝试找到更大的符合条件的索引
        else:
            right = mid - 1
    return result

def find_range(fn, a, b):
    left_bound = find_left_bound(fn, a, b)
    if left_bound == -1:
        return []  # 无真值区间时返回空列表
    right_bound = find_right_bound(fn, left_bound, b)
    return [left_bound, right_bound]

# 测试验证
assert find_range(fn, 0, 1000000000) == [500000000, 700000000]

注意事项 #

• 该算法仅适用于单个连续真值区间的场景，如果存在多个不连续的真值区间，此方法只会返回最左侧的区间边界
• 若序列中不存在任何真值区间，函数会返回空列表，可根据实际需求调整返回逻辑
• 二分查找的边界处理避免了死循环，Python的整数类型无溢出问题，无需额外处理

内容的提问来源于stack exchange，提问作者YouHoGeon