Median of Two Sorted Arrays

Topic: 03. Sorting (Binary Search)

Link: LeetCode 4 - Median of Two Sorted Arrays

1. Logical Breakdown

• [x] Core Logic: Partition arrays such that LeftPart <= RightPart.
• [x] Algorithm: Binary Search on the smaller array.

2. Visualization

graph TD Start["BS on Smaller Array"] --> Calc["Calc Partition X & Y"] Calc --> Valid["Is MaxLeft <= MinRight?"] Valid -- Yes --> Found["Return Median"] Valid -- No --> Adjust["Move Left or Right"] Adjust --> Calc

3. Complexity

• Time: O(log min(N, M))
• Space: O(1)

4. Code

package com.dsa.sorting;

public class MedianOfTwoSortedArrays {
    public double solve(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array for binary search efficiency
        if (nums1.length > nums2.length) return solve(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;

            // If partitionX is 0 it means nothing is there on left side. Use -INF.
            // If partitionX is length of input then there is nothing on right side. Use +INF.
            int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];

            int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                // We have partitioned array at correct place
                if ((x + y) % 2 == 0) {
                    return ((double)Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
                } else {
                    return (double)Math.max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                // We are too far on right side for partitionX. Go on left side.
                high = partitionX - 1;
            } else {
                // We are too far on left side for partitionX. Go on right side.
                low = partitionX + 1;
            }
        }
        return 0.0;
    }
}