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

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.

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.

• Your intuition is correct -it is EXACTLY what a binary search is.. And I don't know if you're allowed to do it, but Java has a binary search built into it docs.oracle.com/javase/7/docs/api/java/util/… Dec 22, 2017 at 20:29
• Arrays.binarySearch is much older than Java 8. If you keep track of your hi and lo variables, it should be straightforward from there. Invite me to a chat room if you need specific debugging help. Dec 22, 2017 at 20:33

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.

• In C++ we have standard library function lower_bound() and upper_bound() for such operations. But for java there is no such standard library function, you have to implement your own version of these functions in java :( Dec 22, 2017 at 19:59
• I fail to see how this is any different than my answer whatsoever except that it doesn't explain how or why it works. Dec 22, 2017 at 20:08