Median of Two Sorted Arrays

L10 Hard Binary Search

Concept

The median splits both arrays so that everything on the left is ≤ everything on the right — binary search finds that split in O(log(min(m, n))).

Given two sorted arrays nums1 and nums2, return the median of the combined sorted array. For even combined length, the median is the average of the two middle values.

Examples

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

→ 2.0

▸ nums1 = [1, 2], nums2 = [3, 4]

→ 2.5

▸ nums1 = [], nums2 = [1]

→ 1.0

Progressive Hints

Hint 1 · Nudge

You only need to place one perfect cut; the median falls out of the two middle values around it.

Hint 2 · Plan

Binary search a cut position i in the smaller array such that the companion cut j in the larger array splits the combined halves evenly and every left value stays at most every right value. The median then comes from the four values bordering the cut.

Hint 3 · Approach

Binary search i in 0..len(smaller). For each i, set j = (total length + 1) / 2 - i, check the left and right bounds, and move i until the split is balanced. Compute the median from the max of the lefts and the min of the rights.

Output

// Run your code to see the output here.