Algorithm to pick values from set to match target value?

Question

I have a fixed array of constant integer values about 300 items long (Set A). The goal of the algorithm is to pick two numbers (X and Y) from this array that fit several criteria based on input R.

Formal requirement:
Pick values X and Y from set A such that the expression X*Y/(X+Y) is as close as possible to R.

That's all there is to it. I need a simple algorithm that will do that.

Additional info:
The Set A can be ordered or stored in any way, it will be hard coded eventually. Also, with a little bit of math, it can be shown that the best Y for a given X is the closest value in Set A to the expression X*R/(X-R). Also, X and Y will always be greater than R

From this, I get a simple iterative algorithm that works ok:

int minX = 100000000;
int minY = 100000000;
foreach X in A
    if(X<=R)
        continue;
    else
        Y=X*R/(X-R)
        Y=FindNearestIn(A, Y);//do search to find closest useable Y value in A
        if( X*Y/(X+Y) < minX*minY/(minX+minY) )
        then
            minX = X;
            minY = Y;
        end
    end
end

I'm looking for a slightly more elegant approach than this brute force method. Suggestions?

Answer 1

For a possibly 'more elegant' solution see Solution 2.

---

Solution 1)

Why don't you create all the possible 300*300/2 or (300*299/2) possible exact values of R, sort them into an array B say, and then given an R, find the closest value to R in B using binary search and then pick the corresponding X and Y.

I presume that having array B (with the X&Y info) won't be a big memory hog and can easily be hardcoded (using code to write code! :-)).

This will be reasonably fast: worst case ~ 17 comparisons.

---

Solution 2)

You can possibly also do the following (didn't try proving it, but seems correct):

Maintain an array of the 1/X values, sorted.

Now given an R, you try and find the closest sum to 1/R with two numbers in the array of 1/Xs.

For this you maintain two pointers to the 1/X array, one at the smallest and one at the largest, and keep incrementing one and decrementing the other to find the one closest to 1/R. (This is a classic interview question: Find if a sorted array has two numbers which sum to X)

This will be O(n) comparisons and additions in the worst case. This is also prone to precision issues. You could avoid some of the precision issues by maintaining a reverse sorted array of X's, though.

Answer 2

When the size of the input is (roughly) constant, an O(n*log(n)) solution might run faster than a particular O(n) solution.

I would start with the solution that you understand the best, and optimize from there if needed.

Answer 3

Two ideas come to my mind:

1) Since the set A is constant, some pre-processing can be helpful. Assuming the value span of A is not too large, you can create an array of size N = max(A). For each index i you can store the closest value in A to i. This way you can improve your algorithm by finding the closest value in constant time, instead of using a binary search.

2) I see that you omit X<=R, and this is correct. If you define that X<=Y, you can restrict the search range even further, since X>2R will yield no solutions either. So the range to be scanned is R<X<=2R, and this guarantees no symetric solutions, and that X<=Y.