4. Median of Two Sorted Arrays

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

Examples

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

Solution 1

/**
 * 
 * 
 */

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length < nums2.length) {
            return findMedian(nums1, nums2);
        } else {
            return findMedian(nums2, nums1);
        }
    }
    
    public double findMedian(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int low = 0, high = m;
        while(low <= high) {
            int posx = (low + high)/2;
            int posy = ((m + n + 1)/2) - posx;
            int p = (posx > 0)? nums1[posx-1]: Integer.MIN_VALUE;
            int q = (posx < m)? nums1[posx]: Integer.MAX_VALUE;
            int r = (posy > 0)? nums2[posy-1]: Integer.MIN_VALUE;
            int s = (posy < n)? nums2[posy]: Integer.MAX_VALUE;
            if(p <= s && r <= q) {
                if((m+n) % 2 == 0) {
                    return (Math.max(p, r) + Math.min(q, s))/2.0;
                } else {
                    return Math.max(p, r);
                }
            } else if(p > s) {
                high = posx-1;
            } else {
                low = posx+1;
            }
        }
        throw new IllegalArgumentException("Cannot calculate median..");
    }
}

Follow up