Algorithm to find the largest integer in array

Question

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 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.