Unbounded Binary Search
Given a monotonically increasing function f(x) on positive numbers, find the lowest positive integer x where f(x) > 0. In other words, find a positive number x such that f(i) > 0 for any integer i greater than or equal to x.
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:
A simple solution would be 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 a binary search algorithm. But we can’t apply standard binary search on an unbounded search space since the upper limit of the search space is not known.
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, perform a binary search within the search space [i/2, i] and find the target value x in O(log(x)) time.
Following is the C, Java, and Python program that demonstrates it:
C
|
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; } // find the mid-value in the search space int mid = low + ((high - low) / 2); // if `f(mid)` is positive if (f(mid) > 0) { // return `mid` if it is the first element of the search space or // when f(mid-1) is not positive if (mid == low || f(mid - 1) <= 0) { return mid; } // otherwise, 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); } 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
Java
|
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 |
class Main { // A monotonically increasing function `f(x) = 3x - 100` public static 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 public static int binarySearch(int low, int high) { // base condition (search space is exhausted) if (high < low) { return -1; } // find the mid-value in the search space int mid = low + ((high - low) / 2); // if `f(mid)` is positive if (f(mid) > 0) { // return `mid` if it is the first element of the search space or // when f(mid-1) is not positive if (mid == low || f(mid - 1) <= 0) { return mid; } // otherwise, 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 public static 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); } public static void main(String[] args) { int x = exponentialSearch(); System.out.println("f(x) becomes positive for the first time when x = " + x); } } |
Output:
f(x) becomes positive for the first time when x = 34
Python
|
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 |
# A monotonically increasing function `f(x) = 3x - 100` def f(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 def binarySearch(low, high): # base condition (search space is exhausted) if high < low: return -1 # find the mid-value in the search space mid = low + ((high - low) // 2) # if `f(mid)` is positive if f(mid) > 0: # return `mid` if it is the first element of the search space or # when f(mid-1) is not positive if mid == low or f(mid - 1) <= 0: return mid # otherwise, 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 def exponentialSearch(): # find the range in which the result would reside 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) if __name__ == '__main__': x = exponentialSearch() print('f(x) becomes positive for the first time when x =', x) |
Output:
f(x) becomes positive for the first time when x = 34
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)