0
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

The direct search is in fact the best possible algorithm.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.