  We design an algorithm for finding counterfactuals with strong theoretical
guarantees on its performance. For any monotone model $f : X^d \to \{0,1\}$ and
instance $x^\star$, our algorithm makes \[ {S(f)^{O(\Delta_f(x^\star))}\cdot
\log d}\] queries to $f$ and returns {an {\sl optimal}} counterfactual for
$x^\star$: a nearest instance $x'$ to $x^\star$ for which $f(x')\ne
f(x^\star)$. Here $S(f)$ is the sensitivity of $f$, a discrete analogue of the
Lipschitz constant, and $\Delta_f(x^\star)$ is the distance from $x^\star$ to
its nearest counterfactuals. The previous best known query complexity was
$d^{\,O(\Delta_f(x^\star))}$, achievable by brute-force local search. We
further prove a lower bound of $S(f)^{\Omega(\Delta_f(x^\star))} + \Omega(\log
d)$ on the query complexity of any algorithm, thereby showing that the
guarantees of our algorithm are essentially optimal.
