Optimal generalized bisection method
Take any policy that you like. It will consist in a number of calls to $C$ during which you will reduce the size of the incertainty of the location of $x$.

Whatever rule you use, you can't beat dichotomy, because if you split in unequal subintervals, you can always end-up in the longest, which is longer than the half.

This also holds in the average sense. Assume a split in relative sizes $\alpha$ and $1-\alpha$, which will be performed with these probabilities. The expectation of the relative length after a division is $\alpha^2+(1-\alpha)^2\ge1/2$. The minimum is reached for $\alpha=1/2$.



You might only improve on this result when $x$ is not uniformly distributed and you have some information about this distribution, such as the histogram of frequencies. (In such a case, the optimal rule is probably to split in equiprobable subintervals.)