ealtza
Last Updated: April 12, 2019
·
127
· jg2019

Find the median of two sorted arrays

Find the median of two sorted arrays.

Question:

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

median(arr1, arr2) = 3.5
median(arr1, arr2) = 3.5

Answer:

// Subarray wrapper class
private static class Subarray {
private int[] underlying;
private int start;
private int size;

// 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];
}

}

// Recursively find the median. We remove ~half the items from above and
// below the median on each turn, resulting in O(n log n) runtime
public static double median(int[] arr1, int[] arr2) {
if (arr1.length == 0 || arr1.length != arr2.length) throw new IllegalArgumentException();
return median(Subarray.fromArray(arr1), Subarray.fromArray(arr2));
}

// Recursive function
private static double median(Subarray arr1, Subarray arr2) {
// If each array is length 1, just average the two values
if (arr1.getSize() == 1) {
return (arr1.getFirst() + arr2.getFirst()) / 2.;
}
// If each array is length 2, take the larger first value and the
// smaller second value and average them to get the median
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));

}

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