4. Median of Two Sorted Arrays

Merge both sorted arrays into one sorted array using the merge step of merge sort, then directly pick the median from the middle.

Brute Force

Use two pointers to merge both sorted arrays into a single sorted array. Then find the median: if the total length is odd, return the middle element; if even, return the average of the two middle elements.

Merging takes O(m+n) time and O(m+n) space. This is straightforward but does not achieve the O(log(m+n)) time that the problem ideally requires.

Why it is slow: We process every element when we only need to find the middle value.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) merged[k++] = nums1[i++];
        while (j < nums2.length) merged[k++] = nums2[j++];
        int total = merged.length;
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
}

Binary search on the shorter array to find a partition point where all elements on the left side are less than or equal to all elements on the right side.

Mental Model

Imagine cutting both arrays at some position so that the left halves combined have exactly half the total elements. If we pick the right cut, the largest element on the left side is smaller than the smallest on the right side — that boundary gives us the median.

We binary search on the shorter array's cut position. For each guess, the other array's cut is determined automatically.

Algorithm Steps

1. Ensure nums1 is the shorter array (swap if needed).
2. Let m = len(nums1), n = len(nums2), half = (m + n + 1) // 2.
3. Binary search lo = 0, hi = m on how many elements of nums1 go to the left side.
4. At each step, let i be the cut in nums1, j = half - i the cut in nums2.
5. Compute the four boundary values:
   • left1 = nums1[i-1] if i > 0, else -infinity
   • left2 = nums2[j-1] if j > 0, else -infinity
   • right1 = nums1[i] if i < m, else +infinity
   • right2 = nums2[j] if j < n, else +infinity
6. If left1 <= right2 AND left2 <= right1, we found the correct partition:
   • Odd total: median = max(left1, left2)
   • Even total: median = (max(left1, left2) + min(right1, right2)) / 2
7. If left1 > right2, move hi = i - 1 (too many from nums1).
8. If left2 > right1, move lo = i + 1 (too few from nums1).

Worked Walk-through

nums1 = [1, 3], nums2 = [2], half = 2

Odd total (3). Median = max(1, 2) = 2.0.

Edge Cases

• One array empty: The other array's median is the answer. Binary search on length-0 array finds it in one step.
• Arrays of very different lengths: We always binary search on the shorter one for O(log(min(m,n))).
• All elements equal: Any partition works; the median is that repeated value.

Complexity

• Time: O(log(min(m, n))) — binary search on the shorter array.
• Space: O(1) — only a few variables.