Complexity of generically inverting a class of near linear monotonic functions Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function  $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$;  how many calls to $f$ do we need to brute force $f^{-1}$ as a function of $a$ and $n$?

This problem comes up regularly when you have a near linear monotonic increasing sequence on OEIS which you have a good complexity algorithm to compute it, and need a generic algorithm to get an upper bound on the complexity of computing the inverse.
A simple variant of binary search takes $O(\log a(n))$ time assuming $a(n) = O(n)$ is monotonic.  To compute $f^{-1}(n)$, find $k$ s.t.
$$f(n-2^k) \le n \le f(n+2^k)$$
by trying $k = 0, 1, 2, \ldots$ until the bound holds.  This takes $O(\log a(n))$ steps and produces a window of size $O(a(n))$ which can be finished off with binary search.

Unfortunately, this is the best you can do without a stronger condition on $f(n)$.  Proof sketch: assume that after $O(1)$ queries we've reduced to an interval $[a,b]$ s.t.
$$\begin{aligned}
b-a &amp;\ge c a(n) \\
f(b)-f(a) &amp;= \Theta(a(n))
\end{aligned}$$
Then $f(n)$ within $[a,b]$ is an arbitrary monotonic function subject to the end constraints, and we can adversarily choose $f$ to make $\Theta(\log a(n))$ optimal.