Bracketing a discontinuity in a step function

Question

I have the function

$f(x) = \begin{cases} 0 \:\: (x < a) \\ 1/2 \:\: (x = a)\\ 1 \:\: (x > a) \end{cases}$,

where $a$ is unknown. I can compute the function for any value of $x$, and seek to determine $a$ (to some degree of accuracy).

Given an initial bracket $x_{0} < a < x_{1}$, I subdivide the bracket by defining

$x_{2} := \frac{x_{0}+x_{1}}{2}$

and computing $f(x_{2})$. Then I have either $x_{0} < a < x_{2}$ or $x_{2} < a < x_{1}$. I could proceed with this approach until the bracketing values agree to some accuracy, and thus solve for $a$.

Is there a more efficient algorithm?

Answer 1

No. Although the question is phrased in terms of floating-point arithmetic, this is at heart a question about binary search. Binary search is an optimal algorithm among algorithms that rely on a decision tree (e.g., https://stackoverflow.com/q/4571478/491171). Any data structures and algorithms textbook should discuss this.

Intuitively speaking, if at each step you can make a binary decision (one comparison), you can learn at most one bit of information by partitioning the search region. The optimal behaviour is always to partition the search region in halves. If $a$ can take any of $n=|\mathit{high}-\mathit{low}|/\epsilon_{\mathrm{mach}}$ values, the depth of any (binary) decision tree that contains at least $n$ leaves must be at least $\sim \log_2 n$. Binary search achieves this bound of $\log_2 n$ steps. This analysis applies both the expected behaviour when all $a$'s are equally likely, and also to the worst-case behaviour.

If you have some other information, then it'd be necessary to be more precise about what it means for $a$ to be "unknown", what operations are permitted in the algorithm, and what it means to be "more efficient". (As it is, I interpreted them in the conventional way.)

Answer 2

See @Kirill's answer, but depending on what sort of hardware you have available, you might be able to leverage parallelism to solve the problem more quickly. For example, say you had a way to evaluate $f$ for $P$ operands simultaneously - you could then repeatedly divide your bracket into $P+1$ intervals instead of $2$. Whether this would actually be "more efficient" or faster is difficult to say, as there will be overheads and various definitions of efficiency.