Find two integers with the largest sum within a budget (breaking ties by smallest difference)

Question

The algorithm finds a number pair that is as close to budget as possible, and if there are more pairs with same value, the pair with the least difference shall be given out. My algorithm works correctly, but is far too slow. Do you have ideas to improve it?

limit = highest value within budget atm,
i = smaller number of pair,
j = bigger number of pair

long limit = 0;
long i = 0, j = 0;
Arrays.sort(preis);

for (int a = 0; a < preis.length; a++) {
    for (int b = a + 1; b < preis.length; b++) {
        if (preis[a] + preis[b] > limit && preis[a] + preis[b] <= budget) {
            limit = preis[a] + preis[b];
            i = preis[a];
            j = preis[b];
        } else if (preis[a] + preis[b] == limit) {
            if (preis[a] > i) {
                i = preis[a];
                j = preis[b];
            }
        }
    }
}

I'm using Java 8.

Answer 1

To change your algorithmic order, say from N^2 to N lg N, you must change your algorithm. A simple change will not suffice. But I can think of a better algorithm:

Let us accept the theorum that for each number x in your list, you have a number y such that x + y = z and no other y for the given x will produce a z' where z < z' < budget. That is to say, y is the perfect match for x.

We can use a binary search to find the best y for a given x once the array is sorted.

We can find the y for each x in the array, and the corresponding z. We can loop over these results to find the highest z that does not break the budget, assuming one exists.

The actual code is left as an exercise to the reader, but I think there should be sufficient details to craft it, considering you understand the problem enough to have created a naive solution.

Answer 2

Here is a better solution with time complexity \$0(nlogn)\$:

sort(array)
for each x in array
   use binarySearch() to find value y close to (budget-x)

extend this idea to include other conditions of the problem.