Median of Two Sorted Arrays Solution

Problem

Given two sorted arrays, find the median of the combined sorted sequence without actually merging them. The algorithm must run in O(log(min(m, n))) time.

Input: nums1 = [1, 3], nums2 = [2, 4]
Output: 2.5
Explanation: The combined sorted array is [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5

Counter-example — odd total length: nums1 = [1, 3], nums2 = [2] → combined [1, 2, 3] → median is the single middle element 2.0.

Intuition

The median divides a sorted sequence into two equal halves where every left element is at most every right element. Instead of building that combined array, we can binary search for a partition point in the smaller array: once we know how many elements from nums1 belong on the left, the number from nums2 is determined, and we just need to check if the partition is valid. This collapses O(m+n) work into O(log(min(m,n))).

Approach 1 — Merge and Find Middle

Merge both sorted arrays into a single sorted array, then read off the middle element (or average of two middle elements).

Allocate a result array of length m + n.
Use two pointers to merge both arrays in sorted order.
Once merged, the median is merged[(m+n)//2] for odd total, or (merged[(m+n)//2 - 1] + merged[(m+n)//2]) / 2.0 for even.

1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
2    merged = []
3    i, j = 0, 0
4    while i < len(nums1) and j < len(nums2):
5        if nums1[i] <= nums2[j]:
6            merged.append(nums1[i])
7            i += 1
8        else:
9            merged.append(nums2[j])
10            j += 1
11    # Append any remaining elements from either array
12    merged.extend(nums1[i:])
13    merged.extend(nums2[j:])
14
15    total = len(merged)
16    mid = total // 2
17    if total % 2 == 1:
18        return float(merged[mid])
19    return (merged[mid - 1] + merged[mid]) / 2.0

Time: O(m + n) — we visit every element once during the merge.

Space: O(m + n) — we allocate a new array to hold the combined sequence.

Approach 2 — Binary Search on Partition

Binary search on the partition index of the smaller array. For each candidate split, check whether the four boundary elements form a valid partition; adjust the search window based on which boundary comparison fails.

Ensure nums1 is the shorter array (swap if needed) so the binary search range is minimized.
Let half_len = (m + n + 1) // 2. Binary search on partition1 from 0 to m — this is how many elements from nums1 go on the combined left side.
Derive partition2 = half_len - partition1 — how many elements from nums2 go on the left.
Read the four boundary elements: left1, right1 from nums1, and left2, right2 from nums2. Use −∞ / +∞ when a partition sits at the array edge.
If left1 <= right2 and left2 <= right1, the partition is valid: compute the median from the max of the left sides and the min of the right sides. Otherwise shift the binary search window toward the array with the too-large left boundary.

1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
2    # Always binary search on the shorter array to keep bounds tight
3    if len(nums1) > len(nums2):
4        nums1, nums2 = nums2, nums1
5
6    m, n = len(nums1), len(nums2)
7    half_len = (m + n + 1) // 2  # number of elements on the left side of the combined partition
8
9    low, high = 0, m
10    while low <= high:
11        partition1 = (low + high) // 2
12        partition2 = half_len - partition1
13
14        # Boundary elements around the partition; use sentinels at array edges
15        left1  = nums1[partition1 - 1] if partition1 > 0 else float('-inf')
16        right1 = nums1[partition1]     if partition1 < m else float('inf')
17        left2  = nums2[partition2 - 1] if partition2 > 0 else float('-inf')
18        right2 = nums2[partition2]     if partition2 < n else float('inf')
19
20        if left1 <= right2 and left2 <= right1:
21            # Valid partition found — left max and right min determine the median
22            if (m + n) % 2 == 1:
23                return float(max(left1, left2))
24            return (max(left1, left2) + min(right1, right2)) / 2.0
25        elif left1 > right2:
26            high = partition1 - 1  # nums1's left side is too large; move partition left
27        else:
28            low = partition1 + 1   # nums2's left side is too large; move partition right
29
30    return 0.0  # unreachable for valid input

Time: O(log(min(m, n))) — we binary search only over the shorter array's partition positions.

Space: O(1) — only a constant number of pointers and boundary values.

Complexity Summary

Approach	Time	Space	When to use
Merge Arrays	O(m + n)	O(m + n)	When simplicity matters more than performance
Binary Search on Partition	O(log(min(m, n)))	O(1)	Production use; required when arrays are large

Common Mistakes

Binary searching the longer array — this can make partition2 go negative when partition1 is small; always swap so nums1 is the shorter array before searching.
Wrong half-length formula — using (m + n) // 2 instead of (m + n + 1) // 2 shifts the left half off by one for odd-length totals, causing the wrong element to be returned as the median.
Forgetting partition bounds of 0 and m — the partition index must range [0, m] inclusive, not [1, m-1]; the edge cases (all of nums1 on the right, or all on the left) are valid and common in tests.
Using 0 instead of ±∞ for edge sentinels — when partition1 == 0, there is no left element in nums1; using 0 instead of float('-inf') silently breaks inputs where nums2 contains negative values.
Dividing by integer 2 in the even-length case — (left_max + right_min) / 2 in Java or C++ performs integer division; you must cast to double or use 2.0 to get the correct fractional median.

Median of Two Sorted Arrays — Solution