Median of 2 Sorted Arrays of Different Sizes

Understanding the Problem

The goal is to find the median of two sorted arrays of different sizes.

Method 1: Simple Merge

This method merges the two arrays and finds the median.

def find_median_sorted_arrays(arr1, arr2):
    merged = arr1 + arr2
    merged.sort()
    total = len(merged)
    
    if total % 2 == 0:
        return (merged[total // 2 - 1] + merged[total // 2]) / 2.0
    else:
        return merged[total // 2]

arr1 = [1, 3, 8]
arr2 = [7, 9, 10, 11]
print("Median:", find_median_sorted_arrays(arr1, arr2))
            

Output:

Median: 8.0

Method 2: Binary Search

This method uses binary search to find the median efficiently.

def find_median_sorted_arrays(arr1, arr2):
    n1, n2 = len(arr1), len(arr2)
    if n1 > n2:
        return find_median_sorted_arrays(arr2, arr1)  # Ensure n1 <= n2

    low, high = 0, n1
    while low <= high:
        partition1 = (low + high) // 2
        partition2 = (n1 + n2 + 1) // 2 - partition1

        max_left1 = float('-inf') if partition1 == 0 else arr1[partition1 - 1]
        min_right1 = float('inf') if partition1 == n1 else arr1[partition1]

        max_left2 = float('-inf') if partition2 == 0 else arr2[partition2 - 1]
        min_right2 = float('inf') if partition2 == n2 else arr2[partition2]

        if max_left1 <= min_right2 and max_left2 <= min_right1:
            if (n1 + n2) % 2 == 0:
                return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
            else:
                return max(max_left1, max_left2)
        elif max_left1 > min_right2:
            high = partition1 - 1
        else:
            low = partition1 + 1

    raise ValueError("Input arrays are not sorted.")

arr1 = [1, 3, 8]
arr2 = [7, 9, 10, 11]
print("Median:", find_median_sorted_arrays(arr1, arr2))
            

Output:

Median: 8.0

Method 3: Using a Combined Array

This method combines the arrays and finds the median directly.

def find_median_sorted_arrays(arr1, arr2):
    combined = arr1 + arr2
    combined.sort()
    total = len(combined)
    
    if total % 2 == 0:
        return (combined[total // 2 - 1] + combined[total // 2]) / 2.0
    else:
        return combined[total // 2]

arr1 = [1, 3, 8]
arr2 = [7, 9, 10, 11]
print("Median:", find_median_sorted_arrays(arr1, arr2))
            

Output:

Median: 8.0