4 Median of Two Sorted Arrays

There are two sorted arraysnums1andnums2of 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)

In the given sorted two arrays, we have to find two mid values to find the median. Here, I defined two values: mid1 and mid2 and update them by traversing the arrays until current index is a mid index.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int mid1 = 0, mid2 = 0;
        int m = nums1.length, n = nums2.length;
        int i = 0, j = 0;

        while(i+j < (m+n)/2+1) {
            mid1 = mid2;
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    mid2 = nums1[i];
                    i++;
                } else {
                    mid2 = nums2[j];
                    j++;
                }
            } else if (i < m) {
                mid2 = nums1[i];
                i++;
            } else if (j < n) {
                mid2 = nums2[j];
                j++;
            }
        }

        if ((m+n)%2 == 0) {
            return (double)(mid1+mid2)/2.0;
        }
        return mid2;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        int mid1 = Integer.MIN_VALUE, mid2 = Integer.MIN_VALUE;
        int count = 0, i = 0, j = 0;
        while(count < len/2+1) {
            mid1 = mid2;
            if (i < nums1.length && j < nums2.length) {
                if (nums1[i] < nums2[j]) mid2 = nums1[i++];
                else mid2 = nums2[j++];
            } else if (i < nums1.length)
                mid2 = nums1[i++];
            else mid2 = nums2[j++];
            count++;
        }
        if (len%2 == 0) return (double)(mid1+mid2)/2;
        return mid2; // CHECK: mid2 is median where the length is odd.
    }
}