在布尔数组中查找真实值范围的算法

Question

是否有一种算法可以按顺序查找具有大量元素的范围？

我的理解是，如果存在多个真实区间，则不可能在 O(logn) 时间复杂度内找到所有区间。

即使只有一个真实区间，你也找不到O(logn)以内的区间吗？

因为数组很长（大约10亿），所以需要快速算法。

def fn(idx):
    # In reality, it includes logic that takes 0.5 seconds to determine this index is true or false.
    return 500000000 <= idx <= 700000000


def find_range(fn, a, b):
    ...


assert find_range(fn, 0, 1000000000) == [500000000, 700000000]

Answer 1

不，你无法在 O(log𝑛) 中找到区间。该范围的大小可以为 1，然后面临的挑战是在零的海洋中找到单个 1。没有任何线索可以继续搜索。在最坏的情况下，您将在找到 1 之前先查看所有 0，时间复杂度为 O(𝑛)。

如果知道间隔的最小大小 𝑘，您可以以 𝑘 为步长迭代数组，您一定会在 O(𝑛/𝑘 + 𝑘) 中找到它。