Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return -1;
        }
        
        int m = nums1.length;
        int n = nums2.length;
        
        if ((m + n) % 2 != 0) {
            return (double)findKth(nums1, nums2, (m + n) / 2, 0, m - 1, 0, n - 1);
        } else {
            return (findKth(nums1, nums2, (m + n) / 2, 0, m - 1, 0, n - 1) 
                   + findKth(nums1, nums2, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
        }
    }
    
    int findKth(int[] A, int[] B, int k, int aStart, int aEnd, int bStart, int bEnd) {
        int aLen = aEnd - aStart + 1;
        int bLen = bEnd - bStart + 1;
        
        if (aLen == 0) {
            return B[bStart + k];
        }
        if (bLen == 0) {
            return A[aStart + k];
        }
        if (k == 0) {
            return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
        }
        
        int aMid = aLen * k / (aLen + bLen);
        int bMid = k - aMid - 1;
        
        aMid = aStart + aMid;
        bMid = bStart + bMid;
        
        if (A[aMid] > B[bMid]) {
            k = k - (bMid - bStart + 1);
            aEnd = aMid;
            bStart = bMid + 1;
        } else {
            k = k - (aMid - aStart + 1);
            bEnd = bMid;
            aStart = aMid + 1;
        }
        
        return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
    }
}