Median of Two Sorted Arrays

Given two sorted arrays A1 and A2 of size m and n respectively.
Find the median of the two sorted arrays.

Example :
A1 = [1, 4] 
A2 = [3] 
The median is 3.0

Discussion - 

This is an interesting problem I have come across. Let's discuss

So what is median of a sorted array X. Suppose the size of the array is m
If the m is odd, the median is X[(m / 2) + 1]
If the m is even, the median is (X[m / 2] + X[(m / 2) + 1]) / 2

A simple way is to use the formula:
(X[(m + 1)/ 2] + X[(m + 2)/ 2]) / 2

Above formula works for both odd and even size. E.g. 

when m = 5, the median is:
(X[(5 + 1)/ 2] + X[(5 + 2)/ 2]) / 2 = (X[3] + X[3]) / 2 = X[3]

When m = 6, the median is:
(X[(6 + 1)/ 2] + X[(6 + 2)/ 2]) / 2 = (X[3] + X[4]) / 2

Note the index begins from 1 instead of 0.

Furthermore, for the median of two sorted arrays with size m and n, the formula is:
(X[(m + n + 1)/ 2] + X[(m + n + 2)/ 2]) / 2

By now, the problem is converted to how to get the specific element of two sorted arrays.
Let's define a function to get the kth element of two sorted arrays:

int getKth(int[] A1, int i, int[] A2, int j, int k)

Parameter i is the offset of A1 (i.e. we need search from ith element), and j is the offset of A2.

How to get the kth element of two sorted arrays? 
Let's think about getting the kth element of a single sorted array: 
Obviously we just need to skip k-1 positions and pick up the element in the position k. For two sorted arrays, we are not sure how much positions we need to skip, but let's assume the data layout of the two arrays are the same. so we just try to pick up the element in the position (k/2) for either array. Assume they are mid1 and mid2.

Now we compare mid1 and mid2. If mid1<mid2, it means the kth element cannot be in the first k/2 of A1, so we need to move forward the offset of A1[i] by k/2, half k (k-(k/2)), and call getKth() recursively. If mid1>mid2, do the reverse.

We need to consider some edge cases: 
how about when the offset is out of the range? That means we have excluded all the elements of the array; just set mid1/mid2 to Integer.MAX_VALUE to force the other array is to be handled.

We also need to consider the conditions in the beginning of the function to terminate the recursive calling.

If the offset is out range, we just need to consider the other array; return the kth element of the array immediately (A[offset+k-1]).
If k==1, we just need to compare the first elements of both arrays and return the smaller one.

Java Code -

class Solution {
    public double median(int[] A1,int[] A2) {
        int m=A1.length, n=A2.length, left=(m+n+1)/2, right=(m+n+2)/2;
        return (getKth(A1,0,A2,0,left) + getKth(A1,0,A2,0,right))/2.0;
    }
    
    public int getKth(int[] A1,int i,int[] A2,int j,int k) {
        if(i >= A1.length)return A2[j+k-1];
        if(j >= A2.length)return A1[i+k-1];
        if(k==1)return Math.min(A1[i],A2[j]);
        int mid1 = (i+k/2-1 < A1.length) ? A1[i+k/2-1] : Integer.MAX_VALUE;
        int mid2 = (j+k/2-1 < A2.length) ? A2[j+k/2-1] : Integer.MAX_VALUE;
        return mid1<mid2 ? getKth(A1,i+k/2,A2,j,k-k/2) : getKth(A1,i,A2,j+k/2,k-k/2);
    }
}

Time complexity : Every time we loop, we reduce k/2 elements, so the time complexity is O(log(k)), and k = (m + n)/ 2 , so the final complexity is O(Log(m + n))