Finding the Median of Two Sorted Arrays in Java

JAVA Tutorial
Java File

Introduction

The problem of finding the median of two sorted arrays is a classic coding interview question. The challenge is to find the median efficiently, with a time complexity of O(log(min(m, n))), where m and n are the sizes of the two arrays. In this article, we’ll walk through a Java solution that employs binary search to achieve this efficiency.

Problem Statement

Given two sorted arrays nums1 and nums2, find the median of the two sorted arrays. The overall runtime complexity should be O(log(min(m, n))), where m and n are the sizes of the two arrays.

Approach

To solve this problem, we use a binary search approach on the smaller of the two arrays. The goal is to partition both arrays such that the left half contains all elements less than or equal to the elements in the right half. Here’s a step-by-step explanation:

1. Ensure nums1 is the Smaller Array: For easier binary search, make sure nums1 is the smaller array.
2. Perform Binary Search: Use binary search on nums1 to find the correct partition.
3. Partitioning: Partition both arrays such that the left side contains lower elements, and the right side contains higher elements.
4. Calculate Median: Based on the partitions, calculate the median.

Solution

Here’s a detailed Java implementation of the solution:

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        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;

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

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

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

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();

        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: " + solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0

        int[] nums1_2 = {1, 2};
        int[] nums2_2 = {3, 4};
        System.out.println("Median: " + solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
    }
}

Explanation

1. Initialization: Ensure nums1 is the smaller array.
2. Binary Search: Perform binary search on nums1 to find the correct partition.
3. Partitioning and Median Calculation: Calculate the maximum of the left elements and the minimum of the right elements to find the median.

Conclusion

This binary search approach provides an efficient solution to finding the median of two sorted arrays. By leveraging binary search on the smaller array, the solution achieves a time complexity of O(log(min(m, n))), making it suitable for large input arrays.