Median of Two Sorted Arrays - Python Solution

1. Introduction

The "Median of Two Sorted Arrays" problem is a classic question in algorithm design, often encountered in coding interviews. This problem involves finding the median of two sorted arrays, which is a measure of central tendency. The challenge is to do this efficiently, with a time complexity of O(log (m+n)), where m and n are the sizes of the two arrays. This problem is an excellent test of understanding binary search and divide-and-conquer strategies.

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, the task is to return the median of the two sorted arrays. The solution should have an overall runtime complexity of O(log (m+n)).

2. Solution Steps

1. Identify the smaller of the two arrays to apply binary search.

2. Use binary search to find the correct partition in the smaller array.

3. Ensure that the elements on the left side of the partition are less than or equal to the elements on the right side of the partition in both arrays.

4. Handle edge cases where the partition is at the beginning or end of an array.

5. Calculate the median based on the combined size of the arrays (even or odd).

3. Code Program

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)
    start, end = 0, m

    while start <= end:
        partitionX = (start + end) // 2
        partitionY = (m + n + 1) // 2 - partitionX

        # Handling edge cases
        maxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
        maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
        minX = float('inf') if partitionX == m else nums1[partitionX]
        minY = float('inf') if partitionY == n else nums2[partitionY]

        # Check if partition is correct
        if maxX <= minY and maxY <= minX:
            # Check if combined array is even or odd length
            if (m + n) % 2 == 0:
                return (max(maxX, maxY) + min(minX, minY)) / 2
            else:
                return max(maxX, maxY)
        elif maxX > minY:
            end = partitionX - 1
        else:
            start = partitionX + 1

    raise ValueError("Input arrays are not sorted")

# Testing the function with examples
print(findMedianSortedArrays([1, 3], [2]))
print(findMedianSortedArrays([1, 2], [3, 4]))

Output:

2.0
2.5

Explanation:

1. Array Selection: The algorithm first ensures that binary search is applied on the smaller array.

2. Binary Search: Binary search is used to find the correct partition in the smaller array.

3. Partitioning: The partitions are chosen such that there are equal numbers of elements on both sides, or one more on the left if the total number of elements is odd.

4. Edge Case Handling: Edge cases for partitions at the extremes of the arrays are handled.

5. Median Calculation: The median is calculated based on whether the combined array has an even or odd total number of elements.

6. Correct Partition Check: The algorithm checks if the partition is correct by ensuring the left side elements are less than or equal to the right side elements in both arrays.