Python - Find the Median of Two Sorted Arrays of Different Sizes

Python – Find the Median of Two Sorted Arrays of Different Sizes

This problem is a classic in data structures and algorithms (DSA) interviews. Given two sorted arrays of different sizes, the task is to find the median of the combined sorted array.

In this tutorial, we will break down the problem, review sample inputs and outputs, discuss solution steps, and provide a Python program to solve it.

Problem Statement

You are given two sorted arrays, nums1 and nums2, of sizes m and n respectively. Your goal is to find the median of the two arrays combined. The median is the middle element when the array is sorted. If the total number of elements is even, the median is the average of the two middle elements.

Sample Input and Output

Example 1:

</>

Copy

# Input:
nums1 = [1, 3]
nums2 = [2]

# Output:
Median = 2

Example 2:

</>

Copy

# Input:
nums1 = [1, 2]
nums2 = [3, 4]

# Output:
Median = 2.5

Solution Approach

There are several ways to solve this problem. Two common approaches are:

Merge and Sort Approach:
Merge the two arrays into one, sort the merged array, and then find the median. This method is straightforward and works well for beginners, although its time complexity is O((m+n) log(m+n)).
Optimal Binary Search Approach:
This advanced method uses binary search to partition the arrays and find the median in O(log(min(m, n))) time. While more efficient, it is also more complex to implement.

In this tutorial, we will focus on the Merge and Sort approach for its simplicity and ease of understanding.

Python Program

</>

Copy

# Function to find the median of two sorted arrays using merge and sort
def find_median_sorted_arrays(nums1, nums2):
    # Merge the two arrays
    merged = nums1 + nums2
    # Sort the merged array
    merged.sort()
    
    n = len(merged)
    # If the total number of elements is odd, return the middle element
    if n % 2 == 1:
        return merged[n // 2]
    else:
        # If even, return the average of the two middle elements
        return (merged[(n // 2) - 1] + merged[n // 2]) / 2

# Example 1
nums1 = [1, 3]
nums2 = [2]
print("Example 1 - Median:", find_median_sorted_arrays(nums1, nums2))  # Output: 2

# Example 2
nums1 = [1, 2]
nums2 = [3, 4]
print("Example 2 - Median:", find_median_sorted_arrays(nums1, nums2))  # Output: 2.5

Conclusion

This tutorial demonstrated how to find the median of two sorted arrays of different sizes using the merge and sort approach. While this method is simple and ideal for understanding the concept, it is important to be aware of more optimal solutions like the binary search approach for large datasets.

TutorialKart

Python – Find the Median of Two Sorted Arrays of Different Sizes