Editorial: Median of Two Sorted Arrays

1 Intuition

Instead of merging arrays (O(m+n)), use binary search on the smaller array to find the partition point that divides both arrays into two equal halves (by count of elements).

2 Approach

1. Binary search on smaller array for partition point 2. Find corresponding partition in larger array 3. Ensure all elements on left <= all elements on right 4. Calculate median from partition boundaries

3 Complexity Analysis

**Time Complexity:** O(log(min(m,n))) **Space Complexity:** O(1) Much better than merge approach O(m+n).

4 Solution Code

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    low, high = 0, len(nums1)
    while low <= high:
        cut1 = (low + high) // 2
        cut2 = (len(nums1) + len(nums2) + 1) // 2 - cut1
        left1 = float("-inf") if cut1 == 0 else nums1[cut1-1]
        left2 = float("-inf") if cut2 == 0 else nums2[cut2-1]
        right1 = float("inf") if cut1 == len(nums1) else nums1[cut1]
        right2 = float("inf") if cut2 == len(nums2) else nums2[cut2]
        if left1 <= right2 and left2 <= right1:
            total = len(nums1) + len(nums2)
            return (max(left1, left2) + min(right1, right2)) / 2 if total % 2 else max(left1, left2)
        elif left1 > right2:
            high = cut1 - 1
        else:
            low = cut1 + 1

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) {
        return findMedianSortedArrays(nums2, nums1);
    }
    int low = 0, high = nums1.size();
    while (low <= high) {
        int cut1 = (low + high) / 2;
        int cut2 = (nums1.size() + nums2.size() + 1) / 2 - cut1;
        int left1 = cut1 == 0 ? INT_MIN : nums1[cut1-1];
        int left2 = cut2 == 0 ? INT_MIN : nums2[cut2-1];
        int right1 = cut1 == nums1.size() ? INT_MAX : nums1[cut1];
        int right2 = cut2 == nums2.size() ? INT_MAX : nums2[cut2];
        if (left1 <= right2 && left2 <= right1) {
            return ((nums1.size() + nums2.size()) % 2 == 0)
                ? (max(left1, left2) + min(right1, right2)) / 2.0
                : max(left1, left2);
        } else if (left1 > right2) {
            high = cut1 - 1;
        } else {
            low = cut1 + 1;
        }
    }
    return -1;
}

5 Code Walkthrough

For nums1=[1,3], nums2=[2]: - Binary search in nums1 for partition - Find partition where left side has (1+2)/2=1.5 elements - Left: [1], Right: [2,3] - Median = (1+2)/2 = 1.5