# Search algorithm for an expensive boolean function

I have the following problem. We have a boolean function $$f$$ that is expensive to compute for a given input. We need to find the smallest positive integer $$n$$ such that $$f(n)$$ is true. We don't know anything about $$f$$, i.e., there could be multiple inputs that produce true. We only know that $$n < M$$, where $$M$$ is some maximum limit.

Obviously we could search for $$n$$ one step at a time starting from $$1$$, but this is expensive. Is there a better algorithm?

I tried implementing a nested binary search, but it was very slow for some inputs. The idea is to run binary search between $$1$$ and $$M$$. Say we get some answer $$n'$$ then we know that $$n < n'$$. So now I run a binary search between $$1$$ and $$n'-1$$. I repeat this process until I find the smallest answer from all the binary searches. What am I doing wrong?

To know for sure that $$n$$ is the answer, it is necessary to know all the values $$f(1), \dotsc, f(n)$$. Using the direct search, upon reaching $$n$$, those values will have been obtained, and no other values of $$f$$ will have been obtained.