Median of two Sorted arrays

4.Median of Two Sorted Arrays

Array

Binary Search

Divide and Conquer

Problem Statement:

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

Example:

Input:

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

→

Output:

2.0

Algorithm:

1. Ensure first array is smaller for efficient search
2. Binary search for partition point in smaller array
3. Calculate corresponding partition in larger array
4. Compare elements around partitions
5. Adjust search space based on comparison

Complexity:

Time: O(log(min(m,n))) | Space: O(1)

Java Solution:

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // Ensure nums1 is the smaller array
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int n1 = nums1.length;
    int n2 = nums2.length;
    int low = 0, high = n1;

    // Binary search for the correct partition
    while (low <= high) {
        // Calculate partitions for both arrays
        int partition1 = (low + high) / 2;
        int partition2 = (n1 + n2 + 1) / 2 - partition1;

        // Find elements around partitions
        int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
        int minRight1 = (partition1 == n1) ? Integer.MAX_VALUE : nums1[partition1];
        int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
        int minRight2 = (partition2 == n2) ? Integer.MAX_VALUE : nums2[partition2];

        // Check if partition is valid
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((n1 + n2) % 2 == 0) {
                return (Math.max(maxLeft1, maxLeft2) + 
                        Math.min(minRight1, minRight2)) / 2.0;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        }
        else if (maxLeft1 > minRight2) {
            high = partition1 - 1;
        } else {
            low = partition1 + 1;
        }
    }

    throw new IllegalArgumentException("Input arrays are not sorted or valid.");
}

Python Solution:

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
    # Ensure nums1 is smaller
    if len(nums1) > len(nums2):
        return self.findMedianSortedArrays(nums2, nums1)
        
    n1, n2 = len(nums1), len(nums2)
    low, high = 0, n1
    
    while low <= high:
        # Calculate partitions
        partition1 = (low + high) // 2
        partition2 = (n1 + n2 + 1) // 2 - partition1
        
        # Find elements around partitions
        maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        minRight1 = float('inf') if partition1 == n1 else nums1[partition1]
        maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        minRight2 = float('inf') if partition2 == n2 else nums2[partition2]
        
        if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
            if (n1 + n2) % 2 == 0:
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
            else:
                return max(maxLeft1, maxLeft2)
                
        elif maxLeft1 > minRight2:
            high = partition1 - 1
        else:
            low = partition1 + 1
            
    raise ValueError("Input arrays are not sorted or valid")

C++ Solution:

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    // Ensure nums1 is smaller
    if (nums1.size() > nums2.size()) {
        return findMedianSortedArrays(nums2, nums1);
    }
    
    int n1 = nums1.size(), n2 = nums2.size();
    int low = 0, high = n1;
    
    while (low <= high) {
        // Calculate partitions
        int partition1 = (low + high) / 2;
        int partition2 = (n1 + n2 + 1) / 2 - partition1;
        
        // Find elements around partitions
        int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
        int minRight1 = partition1 == n1 ? INT_MAX : nums1[partition1];
        int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
        int minRight2 = partition2 == n2 ? INT_MAX : nums2[partition2];
        
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((n1 + n2) % 2 == 0) {
                return (max(maxLeft1, maxLeft2) + 
                        min(minRight1, minRight2)) / 2.0;
            } else {
                return max(maxLeft1, maxLeft2);
            }
        }
        else if (maxLeft1 > minRight2) {
            high = partition1 - 1;
        } else {
            low = partition1 + 1;
        }
    }
    
    throw runtime_error("Input arrays are not sorted or valid");
}