If you knew the distribution of $n^*$, you could find an optimal binary decision tree (there are several $O(n\log n)$ algorithms) in terms of expected number of queries (you can't beat binary search if you care about worst case). There are also two simple algorithms which are nearly optimal. I will describe them as algorithms for locating $n^*$ given queries of the form "$n^* \leq x$", which you can easily implement by checking $f(x)$. We assume that the probability that $n^* = i$ is $p_i$.
Gilbert–Moore algorithm: Partition the unit interval $[0,1]$ into intervals of length $p_i$, and let $x_i$ be the midpoint of the $i$th interval. We locate $n^*$ by doing binary search on $[0,1]$. For an interval $I \subseteq [0,1]$, denote by $X(I)$ the midpoints $x_i$ which are found in $I$. We first ask whether $n^* \in X([0,1/2])$. Depending on the answer, we ask whether $n^* \in X([0,1/4])$ or whether $n^* \in X([1/2,3/4])$; and so on. Eventually we reach an interval $I$ such that $X(I)$ is a singleton, and we have found $n^*$.
Horibe's algorithm: Find $x$ that minimizes $|\Pr[n^* \leq x] - 1/2|$, and ask whether $n^* \leq x$. Denote by $I$ the values of $n^*$ conforming to the answer. Find $x$ that minimizes $|\Pr[n^* \leq x \mid n^* \in I] - 1/2|$, and ask whether $n^* \leq x$. Update $I$, and repeat until $I$ becomes a singleton.
Both algorithms find $n^*$ using at most $H(n^*)+2$ queries on average (where $H(n^*)$ is the entropy of $n^*$), compared to the trivial lower bound $H(n^*)$, so they're pretty good.
In your case, you don't know the distribution of $n^*$, but you can make a guess, use one of these algorithms, and hope for the best. If you have several distributions in mind, you can choose one of them to construct an algorithm, and then check their performance on the other distributions, comparing the expected number of queries to the trivial lower bound.
You could also want to optimize some other quantity – for example, the 99th percentile of the number of queries. In that case the algorithms described above will probably still be pretty reasonable.