[LeetCode] Problem 4 - Median of Two Sorted Arrays

Posted on | In ,

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)).

You may assume nums1 and nums2 cannot be both empty.

Example

No.1

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

The median is 2.0

No.2

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n1 = nums1.length;
    int n2 = nums2.length;

    if (n1 > n2)
        return findMedianSortedArrays(nums2, nums1);

    int k = (n1 + n2 + 1) / 2;
    int left = 0;
    int right = n1;

    while (left < right) {
        int m1 = left + (right - left) / 2;
        int m2 = k - m1;

        if (nums1[m1] > nums2[m2 - 1])
            right = m1;
        else
            left = m1 + 1;
    }

    int m1 = left;
    int m2 = k - m1;

    int mid1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1], 
                        m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
    
    if ((n1 + n2) % 2 == 1)
        return mid1;

    int mid2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], 
                        m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);

    return (mid1 + mid2) * 0.5;
}