4. Median Of Two Sorted Arrays

Median of two sorted arrays is a classic programming problem that asks you to find the median value of two sorted arrays without fully merging them. Day to day, this problem is important because it tests your understanding of binary search, array partitioning, edge cases, and time complexity optimization. Instead of combining both arrays and sorting the result, an efficient solution can find the median in O(log(min(m, n))) time, where m and n are the lengths of the two arrays.

Introduction to the Median of Two Sorted Arrays Problem

Given two sorted arrays, the goal is to determine the median of the combined array. The median is the middle value of a sorted list. If the total number of elements is odd, the median is the element exactly in the center. If the total number of elements is even, the median is usually calculated as the average of the two middle elements.

For example:

• [1, 3] and [2] combine into [1, 2, 3], so the median is 2.
• [1, 2] and [3, 4] combine into [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5.

A simple approach would be to merge the two arrays and then find the median. On the flip side, this takes O(m + n) time, which may be inefficient for large arrays. Since both arrays are already sorted, we can do much better using binary search.

Understanding the Median Concept

Before solving the problem efficiently, it is important to understand what the median represents The details matter here..

Suppose the combined array has length N And that's really what it comes down to..

• If N is odd, the median is the element at index N // 2.
• If N is even, the median is the average of the elements at indices N // 2 - 1 and N // 2.

To give you an idea, if the merged array is:

[1, 2, 3, 4, 5]

The median is 3 The details matter here..

If the merged array is:

[1, 2, 3, 4]

The median is (2 + 3) / 2 = 2.5.

The challenge is that we do not want to actually merge the arrays if we can avoid it.

Why Binary Search Is Useful Here

Because both input arrays are sorted, we can use binary search to locate the correct partition between the two arrays.

A partition means dividing the arrays into left and right parts such that every element on the left side is less than or equal to every element on the right side.

For two arrays:

A = [a1, a2, a3, ...]
B = [b1, b2, b3, ...]

We want to choose:

• i elements from array A
• j elements from array B

so that the left side contains half of the total elements.

If the total number of elements is m + n, then the left side should contain:

(leftSize) = (m + n + 1) // 2

The number of elements taken from the second array is:

j = leftSize - i

The partition is valid when:

A[i - 1] <= B[j]
B[j - 1] <= A[i]

These conditions confirm that everything on the left is smaller than or equal to everything

These conditions check that everything on the left is smaller than or equal to everything on the right. When this holds true, we have found the correct partition, and the median can be derived directly from the border elements.

Handling Edge Cases

Partitions can occur at the very beginning or end of an array, meaning one side might be empty. To handle this gracefully without explicit if/else branches for every boundary check, we treat "out of bounds" values as infinities:

• A[i-1] becomes -∞ if i == 0 (nothing on the left of A).
• A[i] becomes +∞ if i == m (nothing on the right of A).
• B[j-1] becomes -∞ if j == 0 (nothing on the left of B).
• B[j] becomes +∞ if j == n (nothing on the right of B).

This simplification allows the comparison logic A[i-1] <= B[j] && B[j-1] <= A[i] to work universally.

The Binary Search Algorithm

We perform binary search on the smaller array to guarantee O(log(min(m, n))) complexity. Let A be the smaller array (length m) and B the larger (length n).

1. Initialize Range: low = 0, high = m.
2. Loop: While low <= high:
   • i = (low + high) // 2 (partition index for A).
   • j = leftSize - i (partition index for B).
   • Check Validity:
     • If A[i-1] > B[j]: We have taken too many elements from A. Move left: high = i - 1.
     • Else if B[j-1] > A[i]: We have taken too few elements from A. Move right: low = i + 1.
     • Else (Valid Partition Found):
       • Max of Left: maxLeft = max(A[i-1], B[j-1]).
       • If total length (m + n) is odd: Return maxLeft.
       • Min of Right: minRight = min(A[i], B[j]).
       • If total length is even: Return (maxLeft + minRight) / 2.0.

Python Implementation

def findMedianSortedArrays(nums1, nums2):
    # Ensure nums1 is the smaller array for log(min(m,n)) complexity
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    low, high = 0, m
    leftSize = (m + n + 1) // 2  # +1 handles both odd/even correctly for left partition size

    while low <= high:
        i = (low + high) // 2      # Partition nums1
        j = leftSize - i           # Partition nums2

        # Handle edge cases with infinities
        maxLeftA  = float('-inf') if i == 0 else nums1[i - 1]
        minRightA = float('inf')  if i == m else nums1[i]
        maxLeftB  = float('-inf') if j == 0 else nums2[j - 1]
        minRightB = float('inf')  if j == n else nums2[j]

Worth pausing on this one.

        # Check if we found the correct partition
        if maxLeftA <= minRightB and maxLeftB <= minRightA:
            # Correct partition found
            if (m + n) % 2 == 1:
                return float(max(maxLeftA, maxLeftB))
            else:
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2.0
        
        elif maxLeftA > minRightB:
            # Too many elements from nums1, move left
            high = i - 1
        else:
            # Too few elements from nums1, move right
            low = i + 1
            
    raise ValueError("Input arrays are not sorted or invalid state reached.")

Complexity Analysis

• Time Complexity: O(log(min(m, n))). The binary search operates exclusively on the smaller array. Each iteration halves the search space.
• Space Complexity: O(1). We only use a constant number of variables for indices and boundary values. No auxiliary arrays or recursion stacks are required.

Conclusion

The Median of Two Sorted Arrays problem is a masterclass in leveraging sorted properties to avoid linear work. By reframing the problem from "finding an element" to "finding a partition," we transform an apparent O(m+n) merge task into a logarithmic search. The key insights—binary searching the smaller array, using infinities to unify edge-case logic, and deriving the median solely from the four border elements—demon

demonstrate the elegance of reducing a seemingly complex merge operation to a binary search on partition boundaries. Day to day, this algorithmic paradigm—treating the median as a dividing line rather than a target value—exemplifies how reframing a problem can yield exponential improvements in efficiency. Beyond its utility as a classic interview question, this technique underpins critical systems in database query optimization, streaming data processing, and distributed computing where merging sorted sequences is routine. By mastering this approach, developers gain not merely a solution to a specific problem, but a transferable intuition for leveraging sorted structures and logarithmic search patterns across a wide spectrum of computational challenges.