Median of Two Sorted Arrays

How it works

We want the median of two sorted arrays without fully merging them.

Think of placing the two arrays side by side and making a cut (partition) so that:

• The left side of the cut contains exactly half of the total elements (or half + 1 if odd).
• All elements on the left side are <= all elements on the right side.

If we can find such a partition, then:

• The median must come from the border elements around this cut:
  • The largest element on the left side,
  • And the smallest element on the right side.

To find this cut efficiently, we:

• Only binary search on the smaller array.
• For a chosen cut in the smaller array, the cut in the larger array is fixed (so total elements on the left is half).
• Check if this partition is valid:
  • Aleft <= Bright and Bleft <= Aright
• If not valid:
  • Move the cut left or right (like normal binary search) until it becomes valid.

Once we have a valid partition, we compute the median using the max of left side and min of right side.

Steps

1. Let the two sorted arrays be A and B. Ensure A is the smaller array (swap if needed).

2. Let:

   • total = len(A) + len(B)
   • half = total // 2

3. Use binary search on A:

   • l = 0, r = len(A) - 1
   • While searching:
     • Let i be the cut index in A (midpoint of l and r).
     • Let j = half - i - 2 be the cut index in B (so that total elements on the left of both arrays equals half).

4. Define border values around the cut:

   • Aleft = A[i] if i >= 0 else -∞
   • Aright = A[i + 1] if i + 1 < len(A) else +∞
   • Bleft = B[j] if j >= 0 else -∞
   • Bright = B[j + 1] if j + 1 < len(B) else +∞

5. Check if the partition is valid:

   • If Aleft <= Bright and Bleft <= Aright:
     • We found the correct partition.
     • If total is odd:
       • Median = min(Aright, Bright)
     • Else (even total):
       • Median = (max(Aleft, Bleft) + min(Aright, Bright)) / 2
   • Else if Aleft > Bright:
     • Move the cut in A left → set r = i - 1.
   • Else (Bleft > Aright):
     • Move the cut in A right → set l = i + 1.

6. Return the median computed from the valid partition.

Complexity

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

Where n is the length of nums1 and m is the length of nums2.

Things to watch for

Binary Searching on the Larger Array

The binary search should be performed on the smaller array to ensure the partition index in the larger array stays within bounds. If you search on the larger array, the computed index j = half - i for the smaller array may become negative or exceed its length, causing index-out-of-bounds errors.

Incorrect Partition Index Calculation

A subtle bug arises from how you define the partition. Some implementations use half = (m + n) / 2 while others use half = (m + n + 1) / 2. Depending on this choice, the indices i and j and the formula for the median differ. Mixing conventions leads to off-by-one errors or incorrect median values.

Mishandling Edge Cases with Empty Partitions

When the partition places all elements of one array on one side (e.g., i = 0 or i = len(A)), the corresponding Aleft or Aright does not exist. You must use sentinel values like negative infinity and positive infinity for these boundary conditions. Accessing A[-1] or A[len(A)] directly causes runtime errors.

Confusing Odd and Even Total Length Cases

For odd total length, the median is a single element; for even, it is the average of two. The element(s) involved depend on whether you are taking the max of the left partition or the min of the right partition. Mixing up which elements to use for each case produces incorrect results.

Forgetting Arrays Are Already Sorted

Some implementations unnecessarily sort the input arrays or merge them fully before finding the median. This ignores the key constraint that the arrays are already sorted, inflating time complexity to O((m+n) log(m+n)) instead of the optimal O(log(min(m, n))).

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2

        if len(B) < len(A):
            A, B = B, A

        l, r = 0, len(A) - 1
        while True:
            i = (l + r) // 2
            j = half - i - 2

            Aleft = A[i] if i >= 0 else float("-infinity")
            Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
            Bleft = B[j] if j >= 0 else float("-infinity")
            Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")

            if Aleft <= Bright and Bleft <= Aright:
                if total % 2:
                    return min(Aright, Bright)
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            elif Aleft > Bright:
                r = i - 1
            else:
                l = i + 1

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int>& A = nums1;
        vector<int>& B = nums2;
        int total = A.size() + B.size();
        int half = (total + 1) / 2;

        if (B.size() < A.size()) {
            swap(A, B);
        }

        int l = 0;
        int r = A.size();
        while (l <= r) {
            int i = (l + r) / 2;
            int j = half - i;

            int Aleft = i > 0 ? A[i - 1] : INT_MIN;
            int Aright = i < A.size() ? A[i] : INT_MAX;
            int Bleft = j > 0 ? B[j - 1] : INT_MIN;
            int Bright = j < B.size() ? B[j] : INT_MAX;

            if (Aleft <= Bright && Bleft <= Aright) {
                if (total % 2 != 0) {
                    return max(Aleft, Bleft);
                }
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
            } else if (Aleft > Bright) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
        return -1;
    }
};