Learning On the Way

4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

A Python solution using Binary search

class Solution: 
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: 
        if len(nums1) < len(nums2): 
            nums1, nums2 = nums2, nums1 
        m, n = len(nums1), len(nums2) 
        sum_length = m + n 
        is_odd = sum_length % 2 == 1 
        target = (sum_length + 1) // 2 
        low = target - n  # The minimum number of elements from array 1 in the first half 
        high = target  # The maximum number of elements from array 1 in the first half 
        while low <= high: 
            num1_in_half = (low + high) // 2  # Number of elements from array 1 in the first half 
            num2_in_half = target - num1_in_half 
            if num1_in_half > 0 and num2_in_half < n and nums1[num1_in_half - 1] > nums2[num2_in_half]: 
                high = num1_in_half - 1 
            elif num2_in_half > 0 and num1_in_half < m and nums2[num2_in_half - 1] > nums1[num1_in_half]: 
                low = num1_in_half + 1 
            else: 
                if num2_in_half == 0: 
                    leftmax = nums1[num1_in_half - 1] 
                elif num1_in_half == 0: 
                    leftmax = nums2[num2_in_half - 1] 
                else: 
                    leftmax = max(nums1[num1_in_half - 1], nums2[num2_in_half - 1]) 
                if is_odd: 
                    return leftmax 
                if num1_in_half == m: 
                    rightmin = nums2[num2_in_half] 
                elif num2_in_half == n: 
                    rightmin = nums1[num1_in_half] 
                else: 
                    rightmin = min(nums1[num1_in_half], nums2[num2_in_half]) 
                return (leftmax + rightmin) / 2

A C++ solution with different idea

int findMedian_logn(int vec1[], int n1, int vec2[], int n2) 
{ 
    int m1 = (n1-1) / 2, m2 = (n2-1) / 2; 
    if(n1 == 1) 
    {
        if(n2 == 1) 
            return vec1[0] < vec2[0] ? vec1[0] : vec2[0]; 
        if(n2 % 2 == 0) 
        { 
            if(vec1[0] >= vec2[m2+1]) 
                return vec2[m2+1]; 
            else if(vec1[0] <= vec2[m2]) 
                return vec2[m2]; 
            else return vec1[0]; 
        } 
        else 
        { 
            if(vec1[0] >= vec2[m2]) 
                return vec2[m2]; 
            else if(vec1[0] <= vec2[m2-1]) 
                return vec2[m2-1]; 
            else return vec1[0]; 
        } 
    } 
    else if(n2 == 1) 
    {
        if(n1 % 2 == 0) 
        { 
            if(vec2[0] >= vec1[m1+1]) 
                return vec1[m1+1]; 
            else if(vec2[0] <= vec1[m1]) 
                return vec1[m1]; 
            else return vec2[0]; 
        } 
        else 
        { 
            if(vec2[0] >= vec1[m1]) 
                return vec1[m1]; 
            else if(vec2[0] <= vec1[m1-1]) 
                return vec1[m1-1]; 
            else return vec2[0]; 
        } 
    } 
    else 
    { 
        int cutLen = n1/2 > n2/2 ? n2/2 : n1/2;
        if(vec1[m1] == vec2[m2])return vec1[m1]; 
        else if(vec1[m1] < vec2[m2]) 
            return findMedian_logn(&vec1[cutLen], n1-cutLen, vec2, n2-cutLen); 
        else 
            return findMedian_logn(vec1, n1-cutLen, &vec2[cutLen], n2-cutLen); 
    } 
}