Given a monotonically increasing function `f(x)`, find the value of x where `f(x)` becomes positive for the first time. In other words, find a positive integer x such that `f(x-1), f(x-2),...` are negative and `f(x+1), f(x+2),...` are positive.

`f(x) <= f(y)`is true for all x and y such that

`x <= y`. For example,

`f(x) = 3x - 100`is a monotonically increasing function. It becomes positive for the first time when x = 34 as shown below:

A simple solution is to consider all positive numbers starting from 0, and find the first number for which `f(x)` is positive. The time complexity of this solution is `O(x)`.

We can solve this problem in `O(log(x))` time with the help of binary search algorithm. But we can't apply standard binary search on an *unbounded* search space since we don't know the upper limit of the search space.

The idea is to determine the range in which x resides using exponential search and perform a binary search within that range. The exponential search routine starts with `i = 1`, and keep on doubling `i` until `f(i)` becomes positive for the first time. When `f(i)` becomes positive, we perform a binary search within the search space `[i/2, i]` and find the target value `x` in `O(log(x))` time.

Here's a C program that demonstrates it:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <stdio.h> // A monotonically increasing function f(x) = 3x - 100 int f(int x) { return 3*x - 100; } // Find the value of x in the search space [low, high] using binary search // where f(x) becomes positive for the first time int binarySearch(int low, int high) { // Base condition (search space is exhausted) if (high < low) return -1; // we find the mid value in the search space int mid = (low + high)/2; // if f(mid) is positive if (f(mid) > 0) { // return mid if it is first element of the search space or // when f(mid-1) is not positive if (mid == low || f(mid - 1) <= 0) return mid; // else discard all elements in the right search space return binarySearch(low, mid - 1); } // if f(mid) is zero or negative, // discard all elements in the left search space return binarySearch(mid + 1, high); } // Returns the positive value x where f(x) becomes positive for the first time int exponentialSearch() { // find the range in which the result would reside int i = 1; while (f(i) <= 0) { // calculate the next power of 2 i *= 2; } // call binary search on [i/2, i] return binarySearch(i/2, i); } // main function int main(void) { int x = exponentialSearch(); printf("f(x) becomes positive for the first time when x = %d", x); return 0; } |

`Output:`

f(x) becomes positive for the first time when x = 34

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply