How to pass a index of the original array from buttom up in a recursive divide-and-conquer solution?

Question

I'm creating a divide-and-conquer algorithm for an HW problem. Given an array, I need to find the index of the highest value (any index if there is multiple). My solution works if I want to return the highest value, but I find difficulty when trying to pass the index from buttom of the stack back up. The array size is different for each level.

    int findLargestPos(int[] arr) {
        int n = arr.length;
        int mid = (int)Math.floor(arr.length / 2);

        if (arr.length <= 1) {
            return 0;
        }

        int[] arr2 = new int[mid];
        int[] arr3 = new int[arr.length - mid];

        copyArr(arr, arr2, 0, 0);
        copyArr(arr, arr3, mid, 0);

        int index1 = findLargestPos(arr);
        int index2 = findLargestPos(arr);

        // Problem starts
        if (value from arr2 is greater than arr3) {
            return arr2 index
        }

        return arr3 index
    }

Answer 1

Instead of creating a class to store the index, you can pass an offset variable to your findLargestPos method that gives you how far away the first element of the array passed to the method is to the right of the first element of the original array passed in from the very first function call.

int findLargestPos(int[] arr, int offset) {
    ...
}

So when first calling findLargestPos, the offset passed should be 0.

findLargestPos(arr, 0)

When making further recursive calls to findLargestPos, the offset passed for the left array should be the offset passed in for the current function call whereas the offset passed for the right array should be the offset passed in for the current function call plus mid.

int index1 = findLargestPos(arr2, offset); // left array
int index2 = findLargestPos(arr3, offset + mid); // right array

However, to get the index from the original array, we also have to change the base condition. Currently, you always return 0 when there is only one or less elements left in the array. Instead, you should pass the offset variable, because this should represent the index of the value in the original array.

if (arr.length <= 1) {
    return offset;
}

Now to address your main concern, how to accurately compare the values at the indexes of the left and right arrays where the greatest values occur. Here's the thing: the indexes returned from the function calls to findLargestPos represent the indexes of the greatest values in the original array. But to access these values in the subarrays, you have to use the offset variables. For example, let's say the original array was split up into two arrays of size 3. If the greatest value in the right subarray corresponds to index 4 in the original array, then this corresponds to index 1 in the right subarray. Since mid in this case comes out to 3, we would subtract offset from the index to get the appropriate index for accessing the value in the right subarray. The same logic applies for the left subarray. So here's what the final method implementation would look like,

public static int findLargestPos(int[] arr, int offset) {
    int n = arr.length;
    int mid = (int)Math.floor(arr.length / 2);

    if (arr.length <= 1) {
        return offset;
    }

    int[] arr2 = new int[mid];
    int[] arr3 = new int[arr.length - mid];

    System.arraycopy(arr, 0, arr2, 0, mid);
    System.arraycopy(arr, mid, arr3, 0, arr.length - mid);

    int index1 = findLargestPos(arr2, offset);
    int index2 = findLargestPos(arr3, offset + mid);

    if (arr[index1 - offset] > arr[index2 - offset]) {
        return index1;
    }

    return index2;
}

Notice that I replaced your calls to copyArr with calls to System.arraycopy.