9
\$\begingroup\$

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.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ Nowadays I switch to C++ whenever all I need is a fast algorithm. Took some effort to understand the differences, but it was absolutely worth it. \$\endgroup\$ – Melissa Loos Dec 17 '18 at 1:11
7
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I will try to invent such a binary search, as I do see why it is much better. It took a while, but now I understand that it is exactly what I do in the game "number guess"(?) //Edit: Exactly is the wrong word, but do I understand that right what happens? \$\endgroup\$ – Melissa Loos Dec 22 '17 at 20:15
  • \$\begingroup\$ 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/… \$\endgroup\$ – corsiKa Dec 22 '17 at 20:29
  • \$\begingroup\$ Yes, that is what I tried first, but as it doens't accept boolean expression I have to write one myself I guess. We are allowed to use anything that is provided by Java V8. \$\endgroup\$ – Melissa Loos Dec 22 '17 at 20:31
  • \$\begingroup\$ 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. \$\endgroup\$ – corsiKa Dec 22 '17 at 20:33
  • \$\begingroup\$ Got that working properly, giving me the perfect match :-) Thanks a lot \$\endgroup\$ – Melissa Loos Dec 22 '17 at 20:48
4
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I tried out the Arrays.binarySearch(), but that only gives me positions of numbers equal to what I search for. I never used binarySearch before though. Do I have to write a method myself or does Java provide one which can handle boolean operations? \$\endgroup\$ – Melissa Loos Dec 22 '17 at 19:54
  • \$\begingroup\$ 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 :( \$\endgroup\$ – snehm Dec 22 '17 at 19:59
  • 1
    \$\begingroup\$ I fail to see how this is any different than my answer whatsoever except that it doesn't explain how or why it works. \$\endgroup\$ – corsiKa Dec 22 '17 at 20:08
  • \$\begingroup\$ I am sorry, I didn't yet respond to your post properly as I was still thinking over it. \$\endgroup\$ – Melissa Loos Dec 22 '17 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.