如何使用 bisect 在需要时计算的数组中进行搜索

Question

bisect.bisect_left((f(x) for x in range(pow(10, 6))), 0)

我正在尝试使用 bisect 对满足f(x) >= 0的最小x进行二分搜索。并且 f(x) 是严格递增的。我使用二分查找的原因是因为计算 f(x) 会消耗大量资源。所以我想尽可能少地计算它。

我在这里遇到的问题是 bisect_left 中的第一个参数需要是一个列表类型，这意味着我必须为每个 x 计算 f(x)。

在这种情况下有没有办法进行二分搜索？

Answer 1

我这里遇到的问题是bisect_left中的第一个参数需要是一个列表类型

不，它没有。它需要是一个序列——一种具有确定长度的类型，支持从 0 开始的索引访问。做一个序列：

import collections
class LazySequence(collections.Sequence):
    def __init__(self, f, n):
        """Construct a lazy sequence representing map(f, range(n))"""
        self.f = f
        self.n = n
    def __len__(self):
        return self.n
    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)

然后您可以将其中之一传递给bisect：

bisect.bisect_left(LazySequence(f, 10**6), 0)