Unbounded Search Sorted Array - C++ Solution

1. Introduction

In this blog post, we tackle a unique problem in algorithmic search, particularly interesting in mathematical computation and analysis. The challenge lies in finding the smallest positive integer x for which a given monotonically increasing function f(x) becomes positive.

Problem

Given a monotonically increasing function f(x) on positive numbers, we need to find the lowest positive integer x where f(x) is greater than 0. This means we are searching for the point where the function starts returning positive values.

2. Solution Steps

1. Start with a small value for x (e.g., x = 1) and double it until f(x) becomes positive.

2. Once we find a range where f(x) changes from negative to positive, perform a binary search in this range.

3. The goal of the binary search is to find the smallest x for which f(x) is positive.

4. Continue the binary search until the exact value of x is found.

3. Code Program

#include <iostream>
using namespace std;

// Example function: f(x) = 2x - 100
int f(int x) {
    return 2 * x - 100;
}

// Function to find the smallest positive x where f(x) > 0
int findPositiveX() {
    int x = 1;

    // Increase x exponentially until f(x) becomes positive
    while (f(x) <= 0) {
        x *= 2;
    }

    // Binary search between x/2 and x
    int left = x / 2, right = x;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(mid) <= 0) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left; // The smallest x where f(x) is positive
}

int main() {
    cout << "Lowest positive integer x for f(x) > 0: " << findPositiveX() << endl;
    return 0;
}

Output:

Lowest positive integer x for f(x) > 0: 51

Explanation:

The function findPositiveX initially finds an upper bound where f(x) becomes positive by exponentially increasing x. Once it finds such a range, it employs binary search between x/2 and x to find the smallest x where f(x) is positive. For the given function f(x) = 2x - 100, the smallest positive integer x where f(x) > 0 is 51, as f(51) = 2.