Skip to content

4. Median of Two Sorted Arrays

Problem:

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

Solutions:

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        int one = findKth(nums1, 0, nums2, 0, (n + 1)/2);
        int two = findKth(nums1, 0, nums2, 0, (n + 2)/2);
        return ((double)one + (double)two )/ 2.0;
    }
    private int findKth(int[] nums1, int s1, int[] nums2, int s2, int k) {
        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 = 0;
        int mid2 = 0;
        if (m1 >= nums1.length) {
            mid1 = Integer.MAX_VALUE;
        }
        else {
            mid1 = nums1[m1];
        }
        if (m2 >= nums2.length) {
            mid2 = Integer.MAX_VALUE;
        }
        else {
            mid2 = nums2[m2];
        }
        if (mid1 < mid2) {
            return findKth(nums1, m1 + 1, nums2, s2, k - k/2);
        }
        else {
            return findKth(nums1, s1, nums2, m2 + 1, k - k/2);
        }
    }
}