Median of Two Sorted Array

The solution derives from merging sorted array. We use two pointers, one points to the first array and other one points to second, both starting from first. We fetch the smaller number of two pointers and move that pointer forward. If we get pointer sum at half of total numbers, it means that we are arriving at median of the merged array.

Code in Python:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        i = j = med1 = med2 = 0
        n = len(nums1) + len(nums2)

        while (i + j) <= n / 2:
            if i < len(nums1) and j < len(nums2):
                med2 = med1
                if nums1[i] < nums2[j]:
                    med1 = nums1[i]
                    i += 1
                else:
                    med1 = nums2[j]
                    j += 1
            elif i < len(nums1):
                med2 = med1
                med1 = nums1[i]
                i += 1
            elif j < len(nums2):
                med2 = med1
                med1 = nums2[j]
                j += 1

        if n % 2 == 0:
            return (med1 + med2) / 2.0
        else:
            return med1

If we want to solve the problem by divide and conquer, we can identify finding median as finding k-th number in two sorted arrays, which is part of quick selection, where k is the median of two sorted arrays.

Code in Java:

public class Solution {

    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
    }

    public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
        if (aStart > A.length - 1) return B[bStart + k - 1];            
        if (bStart > B.length - 1) return A[aStart + k - 1];                
        if (k == 1) return Math.min(A[aStart], B[bStart]);

        int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
        if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
        if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];        

        if (aMid < bMid) 
            return getkth(A, aStart + k/2, B, bStart,       k - k/2);// Check: aRight + bLeft 
        else 
            return getkth(A, aStart,       B, bStart + k/2, k - k/2);// Check: bRight + aLeft
    }
}