CODEWITHSUNDEEP
javaarraysrecursion
Freedom
Freedom

Reputation: 347

Finding Max of an array using Recursion

So it's pretty simple to find the max of an array using a for loop or a while loop, but I wanted to try it out with recursion. For some reason, the substring doesn't work - it says "cannot find symbol". Why is this? My strategy is continue subdividing and comparing the two sides until there is only one left which should be the max....am I doing it right? Thanks

   public static int max(int[] array) {

    if (array.length == 1) {
        return array[0];
    } else {
        int mid = (array.length) / 2;
        int leftmax = max(array.substring(0, mid));
        int rightmax = max(array.substring(mid, array.length));
        if (leftmax > rightmax) {
            return leftmax;
        } else {
            return rightmax;
        }

    }
}

Upvotes: 0

Views: 116

Answers (2)

clcto
clcto

Reputation: 9648

Since array is of type int[] not String, you cannot use substring(). Instead, keep track of which indexes you are searching through. Copying the array each iteration is a waste of both space and time.

int max( int[] array ){ return max( array, 0, array.length - 1 ); }

int max( int[] array, int low, int high )
{
    if (low == high) {
        return array[low];
    } 
    else {
        int mid = (high + low) / 2;
        int leftmax = max(array, low, mid );
        int rightmax = max(array, mid, high );
        if (leftmax > rightmax) {
            return leftmax;
        } 
        else {
            return rightmax;
        }

    }
}

Upvotes: 1

user2591612
user2591612

Reputation:

You are going to want to use Arrays.copyOfRange. Substring isn't going to work on an array.

int[] firstHalf = Arrays.copyOfRange(original, 0, original.length/2);
int[] secondHalf = Arrays.copyOfRange(original, original.length/2, original.length);

I can't comment on your algorithm.

Upvotes: 4

Related Questions