Better alternative to divide and conquer algorithm

Question

First let me explain the problem I'm trying to solve. I'm integrating my code with 3rd party library which does quite complicated financial predictions. For the purposes of this question let's just say I have a blackbox which returns y when I pass in x. Now, what I need to do is find input (x) for a given output (y). Since I know lowest and highest possible input values I wrote the following algorithm:

1. define starting input range (minimum input value to maximum input value)
2. divide the range into two equal parts and find output for a middle value
3. find which half output falls into
4. repeat steps 2 and 3 until range is too small to divide any further

This algorithm does the job nicely, I don't see any problems with it. However, is there a faster way to solve this problem?

Answer 1

It sounds like x and y are strongly correlated (i.e. as x increases, so does y), as otherwise your divide and conquer algorithm wouldn't work.

Assumuing this is the case, and you could work out a correlation factor, then you might be able to multiply the midpoint by the correlation factor to potentially hone in the expected value quicker.

Please note that I've not tested this idea at all, but it's something to think about. Possible improvements would be to make the correlationFactor a moving average, or precompute it based on, say, the deciles between xLow and xHigh.

Also, this assumes that calling f(x) is relatively inexpensive. If it is expensive, then the increased number of calls to f(x) would dwarf any savings. In fact - I'm starting to think this is a stupid idea...

Hopefully the following pseudo-code illustrates what I mean:

DivideAndConquer(xLow, xHigh, correlationFactor, expectedValue)
    xMid = (xHigh - xLow) * correlationFactor
    // Add some range checks to make sure that xMid is within xLow and xHigh!!
    y = f(xMid)
    if (y == expectedValue)
        return expectedValue
    elseif (y < expectedValue) 
        correlationFactor = (xMid - xLow) / (f(xMid) - f(xLow))
        return DivideAndConquer(xLow, xMid, correlationFactor, expectedValue)
    else
        correlationFactor = (xHigh - xMid) / (f(xHigh) - f(xMid))
        return DivideAndConquer(xMid, xHigh, correlationFactor, expectedValue)