Let's consider a strictly decreasing function $f : \mathbb{N} \rightarrow \mathbb{Z}$. That is, $f$ takes as input any natural number $(i ∈ N)$ and returns an integer such that for any $i$, $f(i) > f(i + 1)$. Additionally, $f(0) > 0$. We want to find $n =$ min ${i ∈ N : f(i) ≤ 0}$ . In other words, I'm trying to find the first place where $f$ is at or below the horizontal axis. Assume we can compute $f(i)$ for any input $i$ in constant time.
I know that I can solve the problem in $O(n)$ time by evaluating $f(1), f(2), f(3), . . .$ until I see a non-positive number. But I'm trying to figure out an algorithm that can solve it in $O(log$ $n)$.
Any help would be appreciated.
First note that $n\le f(0)$. Set $k=f(0)-1$; if $f(k)>0$, $n=f(0)$. Otherwise, replace $k$ by $\lfloor k/2\rfloor$; the sign of (the new) $f(k)$ will tell you in which half of the interval $[0,f(0)]$ you'll find $n$. Continuing in similar fashion, you can cut the range of uncertainty in half at each step (modulo some overhead).