3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ "but the input is not sorted" -- why? It's always important to check one's assumptions. $\endgroup$ – Raphael Mar 21 '17 at 21:08
  • $\begingroup$ With a monotone function, you would be right. But if you are lucky and the function is monotonic, then the values of the function are indeed sorted. Because that's what monotonic means ("monotone" means unchanging in pitch. ) $\endgroup$ – gnasher729 Mar 21 '17 at 22:08
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.