Median of Two Sorted Arrays - Java Solution

1. Introduction

This post explores a complex and intriguing problem from the realm of algorithms: finding the median of two sorted arrays. The challenge is to efficiently find the median value in the merged array, ensuring optimal runtime complexity.

Problem

Given two sorted arrays nums1 and nums2 of sizes m and n respectively, the task is to return the median of these arrays combined. The median is the middle value in an ordered list of numbers, and in this case, it should be determined in a way that meets the requirement of O(log(m+n)) runtime complexity.

2. Solution Steps

1. Handle edge cases where one or both arrays are empty.

2. Calculate the total length of the combined arrays.

3. Use a binary search algorithm to find the median by comparing elements of the two arrays.

4. Carefully handle the cases to meet the median definition, especially when the total length is even.

5. Ensure the overall runtime complexity remains O(log(m+n)).

3. Code Program

public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println(findMedianSortedArrays(nums1, nums2)); // Test the function
    }

    // Function to find the median of two sorted arrays
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            // Handling edge cases
            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxX <= minY && maxY <= minX) {
                if ((x + y) % 2 == 0) {
                    return ((double)Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
                } else {
                    return (double)Math.max(maxX, maxY);
                }
            } else if (maxX > minY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }
}

Output:

2.0

Explanation:

1. findMedianSortedArrays: The function implements a binary search to find the median.

2. It ensures that the binary search is always performed on the smaller array for efficiency.

3. The function calculates partitions in both arrays such that elements on the left are less than or equal to elements on the right.

4. It handles edge cases where partitions might be at the extremes of the arrays.

5. The median is calculated based on the combined size (even or odd) of the arrays.

6. If the arrays are not sorted in such a way that allows partitioning to find the median, an exception is thrown.

7. The algorithm ensures a runtime complexity of O(log(min(m,n)) by always performing binary search on the smaller array.