Binary search to find the minimum value above a given value

Question

I have a function that returns a double. The code listing below is an example that I'm using for testing, but the real function will be pulled from an analysis of a data set.

public double f(double x)
{
    return (100000 - x) / 15000;
}

It can be assumed that a higher value of x will always return a lower value, so as x approaches 0 the value returned can potentially increase, but it may always stay at 0.

Values of x will always be positive.

I'd like to be able to find the lowest value of f(x) that is >= to 7 when supplied with a given minimum and maximum value (precision only matters to 0.001). In the example above I'm using 100000 as the maximum value and 1 as the minimum.

Is this a good candidate for a binary search or is there a better alternative?

Answer 1

Yes and no.

If the monotonic function does not converge to a finite value - than yes, you could use binary search as follows:

i <- 1
while (f(i) > target):
   i <- i*2
binary search for target in the range `[2^(i-1),2^i]` for best candidate.

Complexity of the above is O(log(i)) - where i is the index of the closest element.

Note however, that if the function converges to some constant value, all bets are off.
For example, it won't help you to find the closest value to -1 for the function f(i) = 1/i. In this case, thew algorithm will be in an infinite loop.