 Sign-bracketing binary search

Suppose integer endpoints satisfy $l<r$ and $f(l)\le 0<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.