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

Solution:

This question can be converted to find the Kth element of the two arrays. For example, the median of two sorted arrays of size 4 is the (4th element + 5th element) / 2; if the total number of elements is odd, the median element is the k / 2 + 1 th element.

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int size = nums1.length + nums2.length;
    if (size % 2 == 0) {
        return (findKth(size / 2, nums1, nums2, 0, 0) + findKth(size / 2 + 1, nums1, nums2, 0, 0)) / 2.0;
    } else {
        return findKth(size / 2 + 1, nums1, nums2, 0, 0);
    }
}
public int findKth(int k, int[] nums1, int[] nums2, int s1, int s2) {
    if (s1 >= nums1.length) {
        return nums2[s2 + k - 1];
    }
    if (s2 >= nums2.length) {
        return nums1[s1 + k - 1];
    }
    if (k == 1) {
        return Math.min(nums1[s1], nums2[s2]);
    }
    int m1 = s1 + k / 2 - 1;
    int m2 = s2 + k / 2 - 1;
    int mid1 = m1 < nums1.length ? nums1[m1] : Integer.MAX_VALUE;
    int mid2 = m2 < nums2.length ? nums2[m2] : Integer.MAX_VALUE;
    if (mid1 < mid2) {
        return findKth(k - k / 2, nums1, nums2, m1 + 1, s2);
    } else {
        return findKth(k - k / 2, nums1, nums2, s1, m2 + 1);
    }
}