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

Question

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

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

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

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

Answer 1

The problem I encountered here is that the first argument in bisect_left needs to be a list type

不，没有。它需要是一个序列 - 具有确定长度的类型，支持从 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)