4. Median of Two Sorted Arrays

Intuition

The naive approach merges both arrays and picks the middle element - O(m+n). The insight is that we never actually need to merge. Instead, binary search for the correct partition index in the smaller array: once we know how many elements belong in the combined left half, the median falls out directly from the four elements at the boundary.

Algorithm

1Ensure nums1 is the smaller array (swap if needed) to keep binary search on the shorter side.
2Binary search the partition index `cut1` in nums1 from 0 to m. Derive `cut2 = (m+n+1)/2 - cut1` for nums2.
3The partition is valid when maxLeft1 <= minRight2 AND maxLeft2 <= minRight1.
4If maxLeft1 > minRight2, move cut1 left (high = cut1 - 1). If maxLeft2 > minRight1, move cut1 right (low = cut1 + 1).
5Once the partition is valid: if (m+n) is odd, the median is max(maxLeft1, maxLeft2). If even, it is (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.

Example Walkthrough

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

1.Total length = 3 (odd), so we need 2 elements in the left half.
2.Binary search: cut1 = 1 -> maxLeft1 = 1, minRight1 = 3. cut2 = 1 -> maxLeft2 = 2, minRight2 = Infinity.
3.Check: maxLeft1 (1) <= minRight2 (Infinity) and maxLeft2 (2) <= minRight1 (3) - valid partition.
4.Odd total -> median = max(1, 2) = 2.

Output: 2.0

Common Pitfalls

•Use INT_MIN / INT_MAX as sentinels when cut1 = 0 or cut1 = m to avoid array out-of-bounds.
•Calculate mid as lo + (hi - lo) / 2 to avoid integer overflow when lo + hi is large.
•Ensure binary search is on the shorter array so cut2 never goes negative.

4.cs

// Approach: Binary search on the partition point in the smaller array (nums1).
// The goal is to split both arrays so the combined left halves have (m+n)/2 elements,
// and every element on the left is ≤ every element on the right.
// Binary-search the cut index in nums1; derive the cut in nums2 from it.
// If left1 > right2, move the cut left; if left2 > right1, move it right.
// The median is the average of the two middle values (even total) or the larger left value (odd).
// Time: O(log(min(m,n))) Space: O(1)

public class Solution
{
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int n1 = nums1.Length;
        int n2 = nums2.Length;
        if (n1 > n2)
            return FindMedianSortedArrays(nums2, nums1);
        int low = 0, high = n1;
        int n = n1 + n2;
        int left = (n1 + n2 + 1) / 2;
        while (low <= high)
        {
            int mid1 = (low + high) / 2;
            int mid2 = left - mid1;
            int l1 = Int32.MinValue, l2 = Int32.MinValue;
            int r1 = Int32.MaxValue, r2 = Int32.MaxValue;
            if (mid1 < n1)
                r1 = nums1[mid1];
            if (mid2 < n2)
                r2 = nums2[mid2];

            if (mid1 - 1 >= 0)
                l1 = nums1[mid1 - 1];
            if (mid2 - 1 >= 0)
                l2 = nums2[mid2 - 1];

            if (l1 <= r2 && l2 <= r1)
            {
                if (n % 2 == 1)
                    return (double)Math.Max(l1, l2);
                else
                    return (double)(Math.Max(l1, l2) + Math.Min(r1, r2)) / (double)2.0;
            }
            else if (l1 > r2)
                high = mid1 - 1;
            else
                low = mid1 + 1;
        }

        return 0;
    }
}

Was this solution helpful?