Algorithm in O(logn)

I have a project where I should write the following algorithm :


Let an integer function $f\colon\{1,2,3,\ldots,n\} \to \mathbb{Z}$ be monotone and suppose that $f(1) > 0$ and $f(n) < 0$. We would like to find the smallest integer $i$ with $f(i) < 0$. Design an algorithm for this purpose that run in time $O(\log n)4.

I tried to search in the middle ($\frac{n+1}2$) and then go in the right half or in the left half (like binary search) but the input is not sorted. Could someone give me an idea of how I can continue?

This can be viewed as an array with indices given by $1,2,3,\dots,n$ such that $f(i)$ is stored at index $i$.

As $f(i)$ is monotonic, and the sign changes from positive to negative with increasing $i$, it can be concluded that $f(i)$ is a decreasing function, which tells us that the array is sorted in decreasing order.

Here, we are looking for the smallest index $i$ such that $f(i)\lt 0$. We need to find a particular value of $i$ such that $f(i-1)\ge 0$ and $f(i)\lt 0$. Such an $i$ must be unique because for all indices greater than $i$, $f$ must be negative and for all indices less than $i-1$, $f$ must be non negative. Such an $i$ must exist as it is given that for at least one value each, $f$ takes positive and negative values. The index $i$ can be found by binary search as you suggested.

StackExchange Computer Science Q#71855, answer score: 3