Find Median Of Two Sorted Arrays

To find median of two sorted arrays efficiently, you can apply a binary search based algorithm that runs in O(log(min(m, n))) time, where m and n are the lengths of the two arrays. This method avoids merging the arrays and directly computes the median by partitioning the combined data set.

People argue about this. Here's where I land on it.

Introduction

When you need to find median of two sorted arrays, the most intuitive solution is to merge the two arrays into a single sorted list and then pick the middle element(s). Although this approach is simple, it has a time complexity of O(m + n) because every element must be examined. For large inputs, this linear cost can become a bottleneck, especially in interview settings or real‑time applications where performance matters. The optimal solution leverages the inherent ordering of the arrays and uses a binary search technique to achieve logarithmic time. By treating the problem as a search for the correct partition point rather than a full merge, you can find median of two sorted arrays in O(log(min(m, n))) time and O(1) extra space, which is both efficient and elegant.

Steps to Find Median of Two Sorted Arrays

Below is a step‑by‑step guide that walks you through the algorithm. Each step is highlighted with bold text for emphasis.

Step 1: Ensure the first array is the smaller one

• If nums1 is longer than nums2, swap them.
• This guarantees that the binary search runs on the shorter array, minimizing the number of iterations.

Step 2: Perform binary search on the smaller array

• Set low = 0 and high = m (the length of the smaller array).
• While low <= high, calculate partitionX = (low + high) // 2.
• This partitionX splits nums1 into left and right parts.

Step 3: Determine partition points

• Compute partitionY = (m + n + 1) // 2 - partitionX.
• partitionY splits nums2 so that the total number of elements on the left side of both arrays is equal to the total number on the right side (or differs by one when the combined length is odd).

Step 4: Check for correct median condition

• Let maxLeftX, minRightX be the maximum element on the left side of nums1 and the minimum element on the right side, respectively (use -inf/inf for boundaries).
• Let maxLeftY, minRightY be the analogous values for nums2.
• The correct partition satisfies maxLeftX <= minRightY and maxLeftY <= minRightX.
• If the condition is not met, adjust low or high accordingly:
  • If maxLeftX > minRightY, move high = partitionX - 1.
  • Otherwise, move low = partitionX + 1.

Step 5: Compute median value

• When the correct partition is found:
  • If the combined length (m + n) is odd, the median is max(maxLeftX, maxLeftY).
  • If the combined length is even, the median is the average of max(maxLeftX, maxLeftY) and min(minRightX, minRightY).

These steps together constitute a complete procedure to find median of two sorted arrays without ever merging them.

Scientific Explanation

The algorithm’s efficiency stems from the binary search principle applied to the smaller array. By partitioning nums1 at partitionX, we implicitly define a corresponding partition in nums2 (partitionY) that balances the total number of elements on each side. The condition maxLeftX <= minRightY and maxLeftY <= minRightX ensures that every element on the left side is less than or equal to every element on

the right side, which is the fundamental requirement for a valid median. When this condition holds, the median can be directly computed from the boundary elements of these partitions without needing to examine the remaining elements.

This approach leverages the sorted nature of both arrays, allowing us to eliminate half of the search space with each iteration. The logarithmic complexity arises because each binary search step reduces the problem size by a factor of two, making it significantly more efficient than linear approaches for large datasets Simple, but easy to overlook..

This is where a lot of people lose the thread.

Implementation Example

def findMedianSortedArrays(nums1, nums2):
    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    low, high = 0, m
    
    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (m + n + 1) // 2 - partitionX
        
        maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
        minRightX = float('inf') if partitionX == m else nums1[partitionX]
        
        maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
        minRightY = float('inf') if partitionY == n else nums2[partitionY]
        
        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (m + n) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
            else:
                return max(maxLeftX, maxLeftY)
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1

Conclusion

The binary search approach to finding the median of two sorted arrays represents an elegant solution that balances computational efficiency with algorithmic simplicity. This method not only demonstrates the power of divide-and-conquer strategies but also provides a practical tool for efficiently solving problems involving sorted data structures. By carefully partitioning both arrays and leveraging their sorted properties, we achieve optimal O(log(min(m, n))) time complexity while maintaining constant O(1) space usage. Whether in competitive programming or real-world applications, this algorithm stands as a testament to how thoughtful design can yield remarkably efficient solutions And it works..

Edge Case Handling and Robustness

While the core algorithm handles the general case elegantly, a production-ready implementation must explicitly address boundary conditions that can arise with minimal input sizes. The provided Python code implicitly handles many of these through the use of float('-inf') and float('inf') sentinels, but understanding why they work is crucial for porting this logic to languages without native infinity representations (such as C++ or Java) Easy to understand, harder to ignore..

This changes depending on context. Keep that in mind.

Empty Arrays: If nums1 is empty (m = 0), the while loop executes exactly once with partitionX = 0. So naturally, partitionY = (0 + n + 1) // 2, correctly splitting nums2 into two halves. maxLeftX becomes -inf and minRightX becomes +inf. The condition maxLeftX <= minRightY is trivially true, and maxLeftY <= minRightX is also true. The median reduces to the median of nums2 alone, calculated via max(maxLeftY, -inf) (odd) or averaging maxLeftY and minRightY (even) Not complicated — just consistent..

Non-Overlapping Ranges: Consider `nums1 = [1,