4. Median of Two Sorted Arrays

Problem Description

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

Input: nums1 = [1,3], nums2 = [2]
Output: 2.0
Explanation: Merged array = [1,2,3] and median is 2.

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.5
Explanation: Merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Solution Approach

This problem requires a binary search approach to achieve the O(log(m+n)) time complexity:

1. Ensure nums1 is the smaller array for simplicity
2. Apply binary search on the smaller array to find the correct partitioning point
3. Calculate the corresponding partition in the second array
4. Check if we've found the correct partition by comparing the maximum value on the left sides with the minimum value on the right sides
5. Adjust the partition point based on the comparison

The key insight is that we need to find a partition such that:

• All elements to the left of the partition in both arrays are less than or equal to all elements to the right
• The left and right parts have approximately equal sizes

Python Implementation:

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # Ensure nums1 is the smaller array for simpler implementation
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
            
        x, y = len(nums1), len(nums2)
        low, high = 0, x
        
        while low <= high:
            # Partition points
            partitionX = (low + high) // 2
            partitionY = (x + y + 1) // 2 - partitionX
            
            # Edge cases for partition points
            maxX = float('-inf') if partitionX == 0 else nums1[partitionX-1]
            minX = float('inf') if partitionX == x else nums1[partitionX]
            
            maxY = float('-inf') if partitionY == 0 else nums2[partitionY-1]
            minY = float('inf') if partitionY == y else nums2[partitionY]
            
            # Check if we have the correct partition
            if maxX <= minY and maxY <= minX:
                # Even or odd total number of elements
                if (x + y) % 2 == 0:
                    return (max(maxX, maxY) + min(minX, minY)) / 2
                else:
                    return max(maxX, maxY)
            # Adjust the partition
            elif maxX > minY:
                high = partitionX - 1
            else:
                low = partitionX + 1
                
        # This should never be reached if the input arrays are sorted
        raise ValueError("Input arrays are not sorted")