Encontre a mediana de duas matrizes classificadas

Encontre a mediana de duas matrizes classificadas.

Questão:

arr1 = [1, 3, 5]
arr2 = [2, 4, 6]

mediana (arr1, arr2) = 3,5
mediana (arr1, arr2) = 3,5

Responda:

// Classe de wrapper de Subarray
private static class Subarray {
private int [] subjacente;
private int start;
tamanho int privado;

// Get a new subarray that is backed by the input array
private static Subarray fromArray(int[] arr) {
    Subarray s = new Subarray();
    s.underlying = arr;
    s.start = 0;
    s.size = arr.length;
    return s;
}

// Return the subarray from i to j, including i and excluding j
private Subarray subarray(int i, int j) {
    if (i > j) throw new IllegalArgumentException();
    if (j > this.size) throw new IndexOutOfBoundsException();
    Subarray s = new Subarray();
    s.underlying = this.underlying;
    s.start = start + i;
    s.size = j - i;
    return s;
}

// Get the size of the subarray
private int getSize() {
    return size;
}

// Get the first element of the subarray
private int getFirst() {
    return underlying[start];
}

// Get the last element of the subarray
private int getLast() {
    return underlying[start + size - 1];
}

// Get the median of the subarray
private double getMedian() {
    // If it is even length, average the middle elements
    if (size % 2 == 0) 
        return (underlying[start + size / 2 - 1] + 
                underlying[start + size / 2]) / 2.;
    return underlying[start + size / 2];
}

}

// Encontre recursivamente a mediana. Removemos ~ metade dos itens acima e
// abaixo da mediana em cada turno, resultando em O (n log n) tempo
de execução público estático duplo mediano (int [] arr1, int [] arr2) {
if (arr1.length == 0 || arr1.length! = Arr2.length) lança nova IllegalArgumentException ();
retornar mediana (Subarray.fromArray (arr1), Subarray.fromArray (arr2));
}

// Função recursiva
private static double median (Subarray arr1, Subarray arr2) {
// Se cada array tem comprimento 1,
calcule a média dos dois valores if (arr1.getSize () == 1) {
return (arr1.getFirst () + arr2.getFirst ()) / 2 .;
}
// Se cada array tem comprimento 2, pegue o primeiro valor maior e
// o segundo valor menor e faça a média deles para obter a mediana
if (arr1.getSize () == 2) {
return (Math.max (arr1.getFirst (), arr2.getFirst ()) +
Math.min (arr1.getLast (), arr2.getLast ())) / 2 .;
}

double median1 = arr1.getMedian();
double median2 = arr2.getMedian();

// If both arrays have the same median we've found the overall median
if (median1 == median2) return median1;
// For the array with the greater median, we take the bottom half of 
// that array and the top half of the other array
if (median1 > median2) {
    // If the arrays are even length, we want to include the upper/lower
    // half of the array plus one additional element
    return median(arr1.subarray(0, arr1.getSize() / 2 + 1), 
                  arr2.subarray((arr2.getSize() - 1) / 2, arr2.getSize()));
}
// Do the opposite of median1 > median2
return median(arr1.subarray((arr1.getSize() - 1) / 2, arr1.getSize()),
              arr2.subarray(0, arr2.getSize() / 2 + 1));

}

Fonte: https://www.byte-by-byte.com/median/