Searching the most efficient way

ZKR

Honorable
Mar 12, 2012
35
0
10,580
Hey all.
I have to write a method that accepts 2 arrays and checks if any number in Array_B contains the sum of any subsequent members in Array_A.
1. Does subsequent means that if the array is {1, 3, 4, 5} I should compare:

1+3, 3+4, 4+5
OR :

1+3, 4+5 (in pairs)

2. It is said, assume Array_A is sorted, does that mean it is sorted by size and thus affects the method implementation?

3. Is the method I wrote the best and least complex? (it is forbidden to use interfaces in this assignment).

Code:
		public static int equal (int a[], int b[])
		{
		int returnValue = 0;
		
		int sum;
		for (int position = 0; position < a.length-1;  position++)
		{
			sum = a[position] + a[position+1];
			for (int num = 0; num < b.length; num++)
			{
				if (sum == b[num])
					returnValue = 1;
			}
		}
		return (returnValue);
		}

Any help is most appreciated.
 
Solution


Typical attitude of academics - don't ask questions, we know what we're talking about and don't need to explain ourselves. They've probably never written production code in their lives. :lol:

Rather than setting the counters to the array lengths, why not just add a "return 1" statement? Then you can add "return 0" at the end of the method. The returnValue variable is basically redundant, but it's probably a requirement too :pfff:



That is how I'd interpret it, but it's...

randomizer

Distinguished
It could certainly be better. Here are a couple of changes I'd make:

1. Change the method name to something that better describes what it does. You're not testing if the arrays are equal after all. It would also be nice to change th array names to something a bit nicer. Leave single character variable names for counters :)

2. Return a boolean. You are simply returning a true/false flag and a boolean suits this better than an integer. If the assignment requires an integer to be returned, ask the lecturer why, because there doesn't seem to be any reason for it.

3. Return true as soon as you find a match. Don't continue to loop through the arrays, as this just adds an unnecessary overhead. The last statement in the method can be "return false", because you'll only hit this if you have gone through the whole of array a.
 

ZKR

Honorable
Mar 12, 2012
35
0
10,580
" Return true as soon as you find a match. Don't continue to loop through the arrays, as this just adds an unnecessary overhead. The last statement in the method can be "return false", because you'll only hit this if you have gone through the whole of array a. "

Yes I changed it:
Code:
	public static int equal (int a[], int b[])
		{
		int returnValue = 0;
		
		int sum;
		for (int position = 0; position < a.length-1;  position++) // Checks every sum 
		{
			sum = a[position] + a[position+1];
			for (int num = 0; num < b.length; num++)
			{
				if (sum == b[num])	
				{
					returnValue = 1;
					num = b.length;          // HERE`s THE CHANGE, stops the counters in the for loops. here
					position = a.length;    // and here
				}
			}
		}
		return (returnValue);
		}


I can`t change method name type or signature, even array names. They don`t allow that, already asked them to let me.

What about the definition of two consequent elements. Is that like pair by pair or one by one n1+n2, n3+n4 ... OR : n1+n2, n2+n3, n3+n4 ?

Thank for the response.
 

randomizer

Distinguished


Typical attitude of academics - don't ask questions, we know what we're talking about and don't need to explain ourselves. They've probably never written production code in their lives. :lol:

Rather than setting the counters to the array lengths, why not just add a "return 1" statement? Then you can add "return 0" at the end of the method. The returnValue variable is basically redundant, but it's probably a requirement too :pfff:



That is how I'd interpret it, but it's really something that the lecturer needs to explain. After all, they wrote the question and they know what they want you to do.
 
Solution

ZKR

Honorable
Mar 12, 2012
35
0
10,580
Thanks, good advice on the termination. I didn`t do that because I read in the book (a good one actually) that it`s not a good practice to have 2 return statements in the same method.

Now the assignment was corrected by them in the course forum and they underline that the A Array is sorted (we must assume it is).
Does that mean that I should better compare it via Binary search, starting from the unsorted values of Array B them to the mid-Point of A.

If the B value is smaller it can`t be the sum of the bigger numbers after the mid-point, so it would continue with the smaller ones.
Does that make sense?
 

randomizer

Distinguished


You shouldn't abuse return statements, but having more than one in a small method when it is clear why you would want to prematurely return to the caller is fine. It's down to personal preference or whatever is mandated by the code standards where you work/study. Also, it makes a lot more sense and looks a lot neater than forcing the loops to finish by just changing the counter.* Doing so is avoiding a return for the sake of avoiding a return. For all intents and purposes you are doing the same thing anyway.



It sounds fine to me, though it might be overengineering things a little. If efficiency is one of the key assignment requirements then go for it, but just make sure that you don't make your solution so complex that you can't read the code. To be honest, unless your arrays are tens of thousands of elements in size, the performance difference will likely be negligible.

*Having a return statement means another developer who looks at your code only needs to work out why you are leaving the method early. Having the counters suddenly change means another developer has to work out why you are changing the counters, and then why you would want to leave the method early. Both achieve the same outcome but one requires an extra bit of thinking.