如何使用 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)

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

How to use bisect to search in a compute-when-need array

python

binary-search