Unbounded Binary Search - exponential search

The binary search algorithm that we discussed in one of the previous articles makes use of the input bounds (start, end) to calculate the middle element. The middle element is then further used to decide the next search space ignoring the other half.

But what if the upper bound of the sorted input is unknown? How can we still efficiently search for an element in such a scenario?

For example, consider the function \( f(x) = 3x - 100\). We need to find the smallest value of x for which \(f(x) > 0\)

A straightforward approach will be to start from \(x=1\) and check for every value until we find an x for which \(f(x) > 0\). In essence, linear search. But this can be very un-efficient, especially where the possible domain values are substantial.

A variation of the binary search algorithm, also known as exponential search, deals with such use cases. In this algorithm, we find a potential search space using exponential search and then use a binary search algorithm to find the exact index.

Consider the following code example:

public int f(int x){
    return 3 * x - 100;
}
public int searchUnbounded(){
    int i = 1;
    while(f(i) <= 0){
        i *= 2;
    }
    // the last value of i (say prev) before the loop 
    // terminated must have resulted in f(x) < 0 due to 
    // which it was again doubled; 
    // For the current value of i which is 2*prev, f(x) > 0 
    // which means the search space is between prev, and i, 
    // so let's run the BS algo from prev (i.e., i/2) to i
    return binarySearch(i / 2, i);
}

As mentioned in the comments, the while loop in the searchUnbounded method will give us a potential search space to work with. We can then use the binary search algorithm to find the exact index.

public int binarySearch(int start, int end){
    while(start <= end){
        int mid = start + ((end - start) / 2);
        if(f(mid) > 0){
            // if already the lower index or
            // the left element to current fails 
            // the condition
            if(mid == start || f(mid - 1) <= 0){
                return mid;
            }
            end = mid - 1;
        } else{
            start = mid + 1;
        }
    }
    return -1;
}

The overall complexity of the algorithm is \(2* O(log_2(n)) \approx O(log_2(n)\) contributed by the searchUnbounded and binarySearch methods.