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

Question

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

I am trying to use bisect to binary search to the smallest x that satisfies f(x) >= 0. And f(x) is strictly increasing. The reason I am using binary search is because computing f(x) consumes a lot of resources. So I want to compute it as less as possible.

The problem I encountered here is that the first argument in bisect_left needs to be a list type, which means I have to compute f(x) for every x.

Is there a way to do binary search in this case?

Answer 1

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

No it doesn't. It needs to be a sequence - a type with a definite length, supporting access by 0-based index. Make a sequence:

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)

Then you can pass one of these to bisect:

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