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.
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:
// 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)
// 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)
// 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
// 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 x = exponentialSearch();
printf("f(x) becomes positive for the first time when x = %d", x);
f(x) becomes positive for the first time when x = 34
Thanks for reading.