Solution by coderGirl

coderGirl

Approach #1 Modified Binary Search [Accepted]

Intuition

The median of a single sorted array is trivial to find and takes O(1) constant time. For example an array A=[1,2,2,4,9,9] which has even number of elements has median [2,4] at indices 2 and 3. Elements [1,2] are less than or equal to the median elements. Elements [9,9] are larger than the median elements. Thus if the number of elements in the array is odd the median is denoted by floor((n-1)/2) and n/2.

Similarly if the array has odd elements then the median is denoted by element in index floor((n-1)/2) where n is the number of elements in the array. For example for an array A=[1,2,4,9,9] the median is 4 at index 2.

Finding median of two sorted arrays is more difficult and cannot be done in constant time. For example two sorted arrays A=[1,2,3,4,9] and B=[5,6] can be merged into a single sorted array in O(N) time to produce C=[1,2,3,4,5,6,9]. The resulting array has 7 elements with median of 4 denoted by the position floor((n-1)/2). It is possible to do better than O(N) by using a modified binary search in O(log(N)) time.

Modified Binary Search

Because both the arrays are sorted, binary search can be used to search each if the arrays in O(log N) time. The catch is to decide whether the selected element is the median or not in constant time.

Algorithm

Thanks to tyuan73 for the smart code.

The following code works as follows:

The run time of the code depends on the shorter list i.e it is O(log N).
For example if A has only one element while B has 100 elements, the median must be one of A[0], B[49], and B[50] without checking everything else. If A[0] <= B[49], B[49] is the answer; if B[49] < A[0] <= B[50], A[0] is the answer; else, B[50] is the answer.

2)After binary search, we get the approximate location of median. Now we just need to compare at most 4 elements to find the answer. This step is O(1).

The tricky part in this algorithm is to find k. When we are finding the
median of one sorted array then depending on whether the number of elements is
odd or even we need to cut off n-1/2 or n/2 elements. When there are two sorted
list of numbers we need to cut off (n+m-1)/2 numbers.
Thus k specifies the numbers to chop off before midA and midB.

Java

public class Solution {
   public double findMedianSortedArrays(int A[], int B[]) {
    int n = A.length;
    int m = B.length;
    // the following call is to make sure len(A) <= len(B).
    // yes, it calls itself, but at most once, shouldn't be
    // consider a recursive solution
    if (n > m)
        return findMedianSortedArrays(B, A);

    // now, do binary search
    int k = (n + m - 1) / 2;
    int l = 0, r = n; // r is n, NOT n-1, this is important!!
    while (l < r) {
        int midA = (l + r) / 2;
        int midB = k - midA;
        if (A[midA] < B[midB])
            l = midA + 1;
        else
            r = midA;
    }

    // after binary search, we almost get the median because it must be between
    // these 4 numbers: A[l-1], A[l], B[k-l], and B[k-l+1]

    // if (n+m) is odd, the median is the larger one between A[l-1] and B[k-l].
    // and there are some corner cases we need to take care of.
    int a = Math.max(l > 0 ? A[l - 1] : Integer.MIN_VALUE, k - l >= 0 ? B[k - l] : Integer.MIN_VALUE);
    if (((n + m) & 1) == 1)
        return (double) a;

    // if (n+m) is even, the median can be calculated by
    //      median = (max(A[l-1], B[k-l]) + min(A[l], B[k-l+1]) / 2.0
    // also, there are some corner cases to take care of.
    int b = Math.min(l < n ? A[l] : Integer.MAX_VALUE, k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE);
    return (a + b) / 2.0;
}
}

Complexity Analysis

Time complexity : O(log n) where is n is the length of the shortest array as
explained above
Space complexity : O(1)