Python – Find the Median of Two Sorted Arrays of Equal Size

In this tutorial, we will learn how to find the median of two sorted arrays of equal size using Python. This is a common problem in data structures and algorithms (DSA) interviews. We will explain the problem, go through sample inputs and outputs, discuss the solution approach, and provide a Python program that implements the solution.

Problem Statement

Given two sorted arrays arr1 and arr2 of equal size, your task is to find the median of the combined set of numbers. The median is the middle value when all the numbers are arranged in order. If the total number of elements is even, the median is the average of the two middle numbers.

Sample Input and Output

Example 1:

</>
Copy
Input: arr1 = [1, 3, 5]
       arr2 = [2, 4, 6]
Output: 3.5

Example 2:

</>
Copy
Input: arr1 = [1, 2, 3, 4]
       arr2 = [5, 6, 7, 8]
Output: 4.5

Solution Approach

We can solve the problem using the following steps:

  1. Merge the arrays: Combine the two sorted arrays into one and sort the resulting array. Since both arrays are already sorted, you can use a two-pointer approach or simply merge and sort.
  2. Calculate the total number of elements: Let n be the total number of elements in the merged array. Since the arrays are of equal size, n will be even.
  3. Find the median: For an even number of elements, the median is the average of the two middle elements. If the total count were odd, the median would be the middle element.

Python Program

</>
Copy
def find_median_sorted_arrays(arr1, arr2):
    # Merge the two arrays and sort the combined list
    merged = sorted(arr1 + arr2)
    n = len(merged)
    
    # Since the total number of elements is even, compute the median as the average of the two middle elements
    mid1 = n // 2 - 1
    mid2 = n // 2
    median = (merged[mid1] + merged[mid2]) / 2
    return median

# Test Example 1
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
print("Median:", find_median_sorted_arrays(arr1, arr2))  # Expected Output: 3.5

# Test Example 2
arr1 = [1, 2, 3, 4]
arr2 = [5, 6, 7, 8]
print("Median:", find_median_sorted_arrays(arr1, arr2))  # Expected Output: 4.5

Conclusion

In this tutorial, we learned how to find the median of two sorted arrays of equal size by merging them and calculating the median from the combined sorted array.