Unbounded Binary Search

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.


 

A function is called monotonically increasing, if 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:

 
Monotonically increasing function
 

 
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:

 

Download   Run Code

Output:

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

 

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
Notify of