Algorithm to find the largest integer in array
Solution 1
A bug is when encountering length
is odd.
In these cases, you "miss" the middle element.
Example: for input int[] arr = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };
- the element 9
will be compared and checked against itself, but then you reduce the size of length
, you exclude 9
from the array you are going to iterate next.
I believe it can be solved by reducing the problem to ceil(length/2)
instead of length/2
(and handling special case of length==1
)
The other issue as was mentioned in comments is: you need to iterate up to length/2
rather then up to length
, otherwise you are overriding yourself.
Lastly - the sign is wrong.
if(a[i]>a[k])
should be
if(a[i]<a[k])
Remember - you are trying to swap the elements if the first is smaller the the second in order to push the larger elements to the head of your array.
Solution 2
but I don't really get it.. I'm having a hard time "picturing" what's happening here.. But it's not always working.. (though sometimes).
In that case you should use a debugger to step through the code to get a picture of what each line of code does.
What I would do is:
public static int maxOfArray(int[] a) {
int max = a[0];
for (int i : a)
if (max < i)
max = i;
return max;
}
public static int findMaxTheHardWay(int[] array) {
for (int length = array.length; length > 1; length = (length + 1) / 2) {
for (int i = 0; i < length / 2; i++) {
if (array[i] < array[length - i - 1])
array[i] = array[length - i - 1]; // don't need to swap.
}
}
return array[0];
}
public static void main(String... args) {
Random rand = new Random(1);
for (int i = 1; i <= 1000; i++) {
int[] a = new int[i];
for (int j = 0; j < i; j++) a[j] = rand.nextInt();
int max = maxOfArray(a);
int max2 = findMaxTheHardWay(a);
if (max != max2)
throw new AssertionError(i + ": " + max + " != " + max2);
}
}
Solution 3
This is rather a crazy way to solve the problem, but I'll play along.
The problem is in the inner loop.
- You start out with i = 0 and k = length - 1.
- If a[i] > a[k] you swap them.
- ...
- You end up with k = 0 and i = length - 1
- If a[i] > a[k] you swap them.
If you look at that carefully you will notice that if we swapped the elements in the first swap, we will also swap them in the last swap; i.e. we will UNDO the effects of the first swap. And the same applies pair-wise through the entire array slice.
See?
What you need to do is to stop the inner loop half way ... and then take account of the case where length
is odd.
By the way, the reason I called this "rather crazy", because the obvious and simple way is much faster: O(N)
versus O(NlogN)
Solution 4
Here is a solution that fits the specifications that you want (unlike many other here, humm, humm):
final Integer[] input = {1, 2, 6, 32, 4, 44 ,12, 42, 3, 7, 17, 22, 57, 23, 102, 103 };
int half = (input.length / 2);
int mod = input.length % 2;
while (half >= 0) {
for (int i = 0, j = (half * 2) + mod - 1; i <= half && j >= half; i++, j--) {
if (input[i] < input[j]) {
final int tmp = input[i];
input[i] = input[j];
input[j] = tmp;
}
}
if (half == 0) break;
half = half / 2;
mod = half % 2;
}
//Here, input[0] = the biggest number in the original input.
Edit: Added mod, so it works if the last element is the largest..
Solution 5
I think your code is working, you just have to ceil the length / 2 in case of odd array but my tests return proper result:
package org.devince.largestinteger;
import java.util.NoSuchElementException;
public class LargestInteger {
final static int[] input = {1, 2, 6, 32, 4, 44 ,12, 42, 3, 7, 17, 22, 57, 23, 102, 103 };
// final static int[] input = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };
// final static int[] input = {1,3,7};
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(String.valueOf(maxOfArray(input)));
}
public static int maxOfArray(int[] a)
{
int length = a.length;
if(length<1)
throw new NoSuchElementException("Not at least one integer in array");
while (length > 1)
{
int k = length;
for(int i = 0; i < length; i++)
{
k--;
if(a[i]>a[k])
{
int j = a[i];
a[i] = a[k];
a[k] = j;
}
}
length = (int) Math.ceil(length / 2f);
}
return a[0];
}
}
Comments
-
Sti almost 2 years
I am trying to create a method which returns an int - the value of the largest integer in the sent array. The way I want this method to work, is to check the first and the last element of the array in a for-loop, and work their way to the middle. So i = first integer, k = last integer. When
i = 0, k = n-1
(indexes), wheni = 1, k = n-2
if you catch my drift. In every loop it needs to checkif a[i]>a[k]
. Then they switch places. Then I know that the largest number is in the leading half of the array, and then I want it to check that half, so ultimately the largest int is at index 0.I tried like this:
public static int maxOfArray(int[] a) { int length = a.length; if(length<1) throw new NoSuchElementException("Not at least one integer in array"); while (length > 1) { int k = length; for(int i = 0; i < length/2; i++) { k--; if(a[i]<a[k]) { int j = a[i]; a[i] = a[k]; a[k] = j; } } length /=2; } return a[0]; }
..but I don't really get it.. I'm having a hard time "picturing" what's happening here.. But it's not always working.. (though sometimes).
EDIT Also: The array {6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12}; will spit out 17 as the largest number. I realize I have to fix the odd-length bug, but I would like to solve this even-length array first..
-
amit over 11 yearsit does not answer the OPs question.
The way I want this method to work, is to....
-
amit over 11 years(1) it does not answer the OPs question.
The way I want this method to work, is to....
(2) it is not java (Length
field). C# I suspect -
Priyank Patel over 11 years@amit Ok it doesnot answer OPs question but provides an alternative that works.Why not?
-
f_puras over 11 years@amit
num.length
is perfectly right, check Java Arrays for an SO example. -
Baz over 11 years@f_puras It was
num.Length
when this comment was added ;) -
Baz over 11 years@freebird
num.length
is correct,num.Length
is incorrect. Why change it back? -
Vishy over 11 years@amit Added a solution for finding the max the hard way. ;)
-
Sti over 11 yearsThank you, I now realize that an odd-length would damage this, however, I am testing my method with different arrays, some of them working, and the one (so far) that failed was an even-length array = {6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12} setting 17 at the index 0, even though 18 is larger.
-
amit over 11 years@StianF: I believe f_puras's is also correct in his comment. You should iterate up to
length/2
in addition to what I mentioned here. -
Sti over 11 yearsThanks! However, theres still something wrong.. May be something else from my stupid code, but I have now stopped the loop half way
i<length/2
, and I have also realized that I actually swapped the larger integer to the wrong half, but I still get wrong with certain arrays. I.e 6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12. I have not started on the odd-length as this is an even length not yet working.. -
amit over 11 years@StianF: Here you go - the if condition sign is also wrong. I editted the answer to reflect it.
-
Sti over 11 yearsYes, I noticed that, forgot to change the question. That however, did not solve my problem.. I will update my question.
-
Stephen C over 11 yearsYea, if you are shuffling large numbers to the left you gave got the sign of your comparison the wrong way around.
-
Sti over 11 yearsThat is weird.. When I try the array {6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12};, and print it out after the method I get: 17,16,10,14,18,5,4,15,12,11,13,7,1,8,3,2,9,6..
-
amit over 11 years@StianF: Did you fix the odd array length issue? It may occure even for even length array, because you constantly divide the problem (For example length=18, the second iteration will have length=9)
-
amit over 11 yearsYou can fix it by:
length = (int)Math.ceil((double)length/2);
for the modification oflength
. -
Sti over 11 yearsThank you! That fixed it. Beating myself up for not realizing that an even array would possibly eventually become an odd array when dividing it.
-
Stephen C over 11 yearsIf you still can't figure out what the problem in your code is, try adding traceprints or running it using a debugger.
-
Sti over 11 yearsWe figured it out. amit was right. The problem was that I didn't take account of the odd-length arrays. I stupidly chose not to do it, because I got the wrong output when using an even-length array, but as the length of that array was
18
, it would have an odd-length9
in the second turn. Btw, how do I figure out the 0(NlogN) stuff? And what is it called in english? -
Stephen C over 11 years@Stainf - In english, it is called "complexity analysis", and that is "Big O" or "Landau" notation. Wait until they teach it to you, or look it up on Wikipedia :-)