Sti Sti - 17 days ago 5
Java Question

Algorithm to find the largest integer in array

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), when
i = 1, k = n-2
if you catch my drift. In every loop it needs to check
if 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..

Answer

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.

Comments