Median of Two Sorted Arrays

Problem

Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays. The overall run time complexity must be O(log(m+n)).

Example 1

Input: nums1 = [1,3], nums2 = [2]

Output: 2.0

Explanation: Merged: [1,2,3] → median = 2.0

Example 2

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.5

Explanation: Merged: [1,2,3,4] → median = (2+3)/2 = 2.5

Constraints: m, n ≥ 0 | m + n ≥ 1 | Both arrays sorted in non-decreasing order

Partition Visualization

A (nums1)

B (nums2)

maxLeft1

—

minRight1

—

maxLeft2

—

minRight2

—

maxLeft1 ≤ minRight2

maxLeft2 ≤ minRight1

—

Variables

—

i (part A)

—

j (part B)

—

max(maxL1,maxL2)

—

min(minR1,minR2)

—

Binary Search Range on i (0 … m)

Step Logic

Press ▶ Play or Next Step to begin the animation.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Ensure A is the shorter array. Set lo=0, hi=m

Binary search: i = (lo+hi)/2, derive j = (m+n+1)/2 − i

Compute boundary: maxL1, minR1, maxL2, minR2 (use ±∞ at edges)

If maxL1 > minR2: i too large → hi = i−1

If maxL2 > minR1: i too small → lo = i+1

Valid partition → compute median from boundary elements

Time

O(log min(m,n))

Space

O(1)

Key Insight

We binary-search on partition index i in the shorter array A. For any i, we know exactly how many elements go into the left half from B: j = ⌊(m+n+1)/2⌋ − i.

The partition is valid when maxL1 ≤ minR2 and maxL2 ≤ minR1 — meaning the combined left side truly contains the ⌊(m+n)/2⌋ smallest elements.

For odd total: median = max(maxL1, maxL2).
For even total: median = (max(maxL1,maxL2) + min(minR1,minR2)) / 2.