= Sign-bracketing binary search
{title2=$f(l)\leq0<f(r)$}
Suppose <integer> endpoints satisfy $l<r$ and $f(l)\leq0<f(r)$. Repeatedly test an interior midpoint and replace the endpoint with its matching sign. The <loop invariant> is the ordered opposite-sign bracket. The positive <integer> width is a <loop variant>, and at termination $r=l+1$. Thus an adjacent sign transition can be located in $O(\log(r-l))$ evaluations without assuming that $f$ is monotone. If $f$ extends continuously between the endpoints, the <intermediate value theorem> associates the sign bracket with a zero. This is different from finding the first true position of a globally monotone predicate.
Back to article page
