Optimal generalized bisection method Suppose I'm looking for a some unknown number $x$ in the interval $[a,b]$ under the following assumptions:


$x$ is unique.
Given any $t \in [a,b]$ I can check, at some fixed computational cost, whether $t&gt;x$. Let's call this operation $C(t)$.


Let $\epsilon&gt;0$ be some small number. I'm interested in efficient algorithms to find an interval $I$, containing $x$, with length $&lt;\epsilon$. The bisection method begins by using $C((a+b)/2), $ halving $[a,b]$, and repeating the process 
 over $\log_2 \left((b-a)/\epsilon \right)$ times. I was wondering if there are more efficient modifications to it, such as breaking the interval into 3 or 4 subintervals at each iteration. Any other efficient alternative is also welcome. Thank you!

P.S. One can assume that $x$ is distributed uniformly in $[a,b]$, and that this process needs to be done many times for different $x$s.
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.)