Median of 2 Sorted Arrays of Equal Size

Understanding the Problem

The goal is to find the median of two sorted arrays of equal size.

Method 1: Simple Merge

This method merges the two arrays and finds the median.

def findMedianSortedArrays(arr1, arr2):
    merged = sorted(arr1 + arr2)
    n = len(merged)
    return (merged[n // 2 - 1] + merged[n // 2]) / 2.0

arr1 = [1, 3]
arr2 = [2, 4]
print("Median:", findMedianSortedArrays(arr1, arr2))
            

Output:

Median: 2.5

Method 2: Binary Search

This method uses binary search to find the median efficiently.

def findMedianSortedArrays(arr1, arr2):
    import sys
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1
    x, y = len(arr1), len(arr2)
    low, high = 0, x
    
    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (x + y + 1) // 2 - partitionX
        
        maxLeftX = -sys.maxsize if partitionX == 0 else arr1[partitionX - 1]
        minRightX = sys.maxsize if partitionX == x else arr1[partitionX]
        
        maxLeftY = -sys.maxsize if partitionY == 0 else arr2[partitionY - 1]
        minRightY = sys.maxsize if partitionY == y else arr2[partitionY]
        
        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (x + y) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0
            else:
                return max(maxLeftX, maxLeftY)
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1

arr1 = [1, 3]
arr2 = [2, 4]
print("Median:", findMedianSortedArrays(arr1, arr2))
            

Output:

Median: 2.5

Method 3: Using a Combined Array

This method combines the arrays and finds the median directly.

def findMedianSortedArrays(arr1, arr2):
    combined = arr1 + arr2
    combined.sort()
    n = len(combined)
    return (combined[n // 2 - 1] + combined[n // 2]) / 2.0

arr1 = [1, 3]
arr2 = [2, 4]
print("Median:", findMedianSortedArrays(arr1, arr2))
            

Output:

Median: 2.5