Median of Two Sorted Arrays of Different Sizes (Binary Search Approach)

1. Problem Statement & Status Quo

Given two sorted arrays, arr1 and arr2, of potentially different sizes ($N_1$ and $N_2$), our objective is to find the median of the combined elements.

Why the Naive Approach Fails

• Naive Strategy: Merge both sorted arrays into a single sorted array of size $N_1 + N_2$, then pick the middle element (for odd total length) or average the two middle elements (for even total length).
• Time Complexity: $O(N_1 + N_2)$ because we must traverse and combine all elements.
• Production Bottleneck: This linear approach causes Time Limit Exceeded (TLE) errors in competitive programming and high-performance interviews when $N_1$ and $N_2$ are massive. We need an optimized logarithmic approach.

2. Core Mental Model: The Symmetry Approach

Since both arrays are already sorted, we can harness Binary Search to achieve an $O(\log(\min(N_1, N_2)))$ time complexity.

Instead of physically merging arrays, we visualize a hypothetical combined sorted array and draw a symmetry line right down the middle to divide it into a left half and a right half.

Real-Life Analogy: Splitting a Line of People by Height

Imagine lining up two separate rows of people, each already sorted by height. To divide them into two equal groups (a left group and a right group) without fully merging the rows, you decide how many people to take from Row 1. Once you pick $X$ people from Row 1, the exact number of people needed from Row 2 is automatically locked in to satisfy the total size of the left half. If the tallest person in the left group from either row is shorter than or equal to the shortest person in the right group, you have successfully formed a valid split!

3. Step-by-Step Evolution of Left/Right Partitions

Let's examine an example where:

• arr1 length $N_1 = 6$: [1, 3, 4, 7, 10, 12]
• arr2 length $N_2 = 4$: [2, 3, 6, 15]
• Total Elements: $10$ (Even)
• Required Left Half Size: $\frac{10}{2} = 5$ elements.

Testing Partition Candidates for Array 1

1. Pick 0 from Array 1:
   • Need $5 - 0 = 5$ from Array 2 (impossible since Array 2 only has 4 elements). $\rightarrow$ Invalid
2. Pick 1 from Array 1:
   • Pick $5 - 1 = 4$ from Array 2.
   • Left: [1] (from arr1), [2, 3, 6, 15] (from arr2)
   • Right: [3, 4, 7, 10, 12]
   • Check: Maximum on left ($15$) is greater than minimum on right ($3$). $\rightarrow$ Invalid Symmetry
3. Pick 2 from Array 1:
   • Left: [1, 3], [2, 3, 6]
   • Check: Max element on left ($6$) > Min element on right ($4$). $\rightarrow$ Invalid Symmetry
4. Pick 3 from Array 1:
   • Left: [1, 3, 4] (3 elements from arr1), [2, 3] (2 elements from arr2)
   • Right: [7, 10, 12] (from arr1), [6, 15] (from arr2)
   • Check:
     • Max left elements: $4$ (from arr1), $3$ (from arr2)
     • Min right elements: $7$ (from arr1), $6$ (from arr2)
     • Is entire left smaller than entire right? Yes ($4 \le 6$ and $3 \le 7$). $\rightarrow$ Valid Symmetry!

4. Validating the Symmetry (The Cross-Check Rule)

Once we pick $mid_1$ elements from arr1 and $mid_2$ elements from arr2 (where $mid_2 = \text{total\_left} - mid_1$), we define four boundary pointers:

Array 1:  [... L1 ] | [ R1 ...]
Array 2:  [... L2 ] | [ R2 ...]

• $L_1$: Last element included on the left from arr1 (arr1[mid_1 - 1])
• $R_1$: First element on the right from arr1 (arr1[mid_1])
• $L_2$: Last element included on the left from arr2 (arr2[mid_2 - 1])
• $R_2$: First element on the right from arr2 (arr2[mid_2])

The Validation Condition

A partition is valid if and only if:

Note: We do not need to compare $L_1$ with $R_1$ or $L_2$ with $R_2$ because each individual array is already internally sorted. We only need to check the cross-arrays.

5. Formulating the Median

Once a valid symmetry is established, extracting the median depends on whether the total number of elements ($N_1 + N_2$) is Even or Odd.

Case A: Even Number of Elements

If total elements $= 10$, the median is the average of the maximum element on the left and the minimum element on the right:

Case B: Odd Number of Elements

If total elements $= 5$, we define the left partition size as $\frac{N_1 + N_2 + 1}{2} = 3$.

6. Binary Search Optimization Strategy

To achieve logarithmic time complexity, we must perform our binary search on the smaller array (arr1).

Adjustment Rules (Binary Search Pointers)

• If $L_1 > R_2$: Elements taken from arr1 are too large. We need to move our search space to the left (high = mid1 - 1).
• If $L_2 > R_1$: Elements taken from arr1 are too small. We need to move our search space to the right (low = mid1 + 1).

7. Complete Code Implementation (C++)

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
        // Ensure nums1 is the smaller array to optimize binary search range
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int n1 = nums1.size();
        int n2 = nums2.size();
        
        int low = 0, high = n1;
        int leftSize = (n1 + n2 + 1) / 2;

        while (low <= high) {
            int mid1 = low + (high - low) / 2;
            int mid2 = leftSize - mid1;

            // Calculate L1, L2, R1, R2 with boundary edge cases
            int l1 = (mid1 == 0) ? INT_MIN : nums1[mid1 - 1];
            int l2 = (mid2 == 0) ? INT_MIN : nums2[mid2 - 1];
            int r1 = (mid1 == n1) ? INT_MAX : nums1[mid1];
            int r2 = (mid2 == n2) ? INT_MAX : nums2[mid2];

            // Check if we found the valid symmetry
            if (l1 <= r2 && l2 <= r1) {
                // If total elements are odd
                if ((n1 + n2) % 2 == 1) {
                    return std::max(l1, l2);
                }
                // If total elements are even
                return (double)(std::max(l1, l2) + std::min(r1, r2)) / 2.0;
            }
            // If l1 is too large, move left
            else if (l1 > r2) {
                high = mid1 - 1;
            }
            // If l2 is too large, move right
            else {
                low = mid1 + 1;
            }
        }

        return 0.0;
    }
};

8. Complexity Analysis

9. Summary and Key Takeaways

• Problem Nature: Finding the median of two sorted arrays can be reframed as finding a correct partition symmetry where the left half elements are smaller than or equal to the right half elements.
• Binary Search on Smaller Array: Always execute binary search on the smaller array (min(N_1, N_2)) to guarantee optimal $O(\log N)$ performance.
• Dynamic Partitioning: mid_1 determines the cut on the first array, while mid_2 is statically derived from the total left partition size requirement ((N1 + N2 + 1) / 2 - mid1).
• Edge Value Handling: Use INT_MIN for out-of-bound left elements and INT_MAX for out-of-bound right elements to ensure cross-comparisons never fail on array boundaries.
• Parity Handling: Odd total element counts return $\max(L_1, L_2)$, while even total element counts average $\max(L_1, L_2)$ and $\min(R_1, R_2)$.
• Space Optimization: Avoiding physical array merging reduces auxiliary space consumption to absolute zero ($O(1)$ space).