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.