Efficient search strategy in a monotonic boolean function wherein the probability of solution location is known apriori

Question

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$

The goal is to search for $n\ast$. The bounds $n_{min}$ and $n_{max}$ are known apriori.

A salient property of $n\ast$ is that it has a higher probability of lying in a region around $\hat{n}$ (known apriori). The exact probability distribution, although unknown, (probably doesn't matter) can be considered as continuous CDF having a higher weighting factor around $\hat{n}$

I have already implemented a simple binary search, but I am looking for more efficient solutions that somehow account for the given probability information (i.e. $n\ast$ is concentrated around $\hat{n}$), I am looking for an efficient algorithm to find $n\ast$. without losing accuracy.

I know that Binary search is worst-case $\mathcal{O}(log\ n)$, but $f(n)$ is so computationally expensive that I can't afford even this.

Answer 1

Since you have no derivatives for your function, you cannot beat bisection search in some asymptotic sense. But you can try to find good starting points for the bisection search.

For example, find $x_0$ so that $F(x_0)=\frac 12$ -- i.e., the most likely point for the switch point. Then, if $f(x_0)=0$, use $x_0$ as the left end point of your starting interval for the bisection search; otherwise, use it as the right starting point. In any case, $x_0$ is likely to be close to the final solution.

For the other starting point of your interval, let's assume for a moment that you had $f(x_0)=1$ -- i.e., that we are looking for a left end point $a_0$ of the interval, with $b_0=x_0$ being the right one. Try, for example, $\alpha$ as the point that is one standard deviation away from $b_0$, i.e., choose $\alpha$ so that $F(\alpha)=(1-0.95)=0.05$. If indeed $f(\alpha)=0$, then set $a_0=\alpha$ and you know that the switch point is in the interval $[a_0,b_0]$. If on the other hand, $f(\alpha)=1$, then the switch point is in fact to the left of $\alpha$, and you would set $b_0=\alpha$ and try again with $\alpha$ so that $F(\alpha)=(1-0.95)^2=0.05^2$. Then repeat until you finally have a starting interval where $f(a_0)\neq f(b_0)$. With this, you would then start your bisection search.