← DSA Atlas
Dedicated problem page · #4

Median of Two Sorted Arrays

HardBinary SearchBinary search on the partitionBinary search over the smaller array's split point
Solve on LeetCode ↗
04
HardBinary SearchBinary search over the smaller array's split pointBinary search on the partition

Median of Two Sorted Arrays

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

Open official problem prompt ↗
In plain English

Compute the median of two sorted arrays as if they were merged, but in logarithmic time by locating the correct split instead of building the merge.

Picture it like this

Like two sorted stacks of numbered cards laid side by side: you slide a divider across both stacks at once until every card left of it is smaller than every card right of it. That divider marks the median.

Example
Input
nums1 = [1, 3], nums2 = [2]
Output
2.0
Why
Merged the arrays are [1, 2, 3]; the middle element of an odd-length total is 2.
Constraints
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
Pattern lesson

See the pattern, then code

Binary search on the partition
Recognition clue

Two already-sorted arrays plus a strict O(log(m+n)) requirement rules out merging and points to a binary search over partition positions.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. The median splits the combined array into a left half and right half of equal size; you only need to find where to cut each array so that every left element is <= every right element, never merging anything.

New words, made simpleKnow these before the algorithm
Partition / cut
An index that divides an array into a left group and a right group.
Left-half size (half)
(m+n+1)//2, how many elements belong to the combined left side.
Sentinel infinity
Using +/- infinity when a cut sits at an array edge so comparisons stay valid.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Merge both arrays

Simple but linear, failing the log-time requirement.

Merge into one sorted array then index the middle.

Time O(m + n)Space O(m + n)
Advance a merge pointer halfway

Constant space but still linear time.

Two-pointer walk to the (m+n)/2-th element without storing.

Time O(m + n)Space O(1)
Best choiceBinary search the partition

Meets the required bound and is the intended solution.

Binary-search the cut in the shorter array; the other cut is derived.

Time O(log(min(m, n)))Space O(1)
The rule we keep true

Invariant

The left partition always contains exactly half = (m+n+1)//2 elements, and the correct answer's cut lies within [lo, hi] of the shorter array.

Why this is correct

Reasoning

Fixing the total left size to half means choosing i in A forces j = half - i in B. The cut is correct precisely when A[i-1] <= B[j] and B[j-1] <= A[i]; both hold at exactly one i because increasing i raises A's left max and lowers B's, moving monotonically. Sentinels handle empty sides so the max/min for the median are always well defined.

The algorithm in three movesSay these aloud before coding
1Ensure you binary-search the shorter array to keep the range small

swap so A=[2], B=[1,3]; m=1, n=2, half=2

2Pick a cut i in the short array; the cut j in the other is forced by half = (m+n+1)//2

i=1, j=1 -> aLeft=2, aRight=inf, bLeft=1, bRight=3

3Read the four boundary values around both cuts, using +/- infinity past the ends

2 <= 3 and 1 <= inf -> odd total -> median = max(2,1) = 2.0

4If the left maxes are <= the opposite right mins, the cut is correct; otherwise move i left or right

5Combine the boundary values for the odd or even median

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
1 · Readnums1=[1,3], nums2=[2]
2 · AskWhich array is shorter?
3 · Update stateswap -> A=[2], B=[1,3], half=2
4 · Resultbinary-search i in [0,1]
Key takeaway

The merged view [1,2,3] has its median at the single middle slot, value 2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Search the shorter array

    Swapping so A is the shorter array bounds the binary search by min(m, n) and keeps j non-negative.

  2. 2
    Lines 12-15Boundary values with sentinels

    Infinities let a cut sit at index 0 or the end without special-casing empty halves.

  3. 3
    Lines 16-19Correct-cut test and median

    When both cross-comparisons hold, the median is the max of the left boundaries (odd) or its average with the min right boundary (even).

  4. 4
    Lines 20-23Move the cut

    If A's left is too big, shrink i; otherwise B's left is too big so grow i.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • One array empty (m = 0)
  • All elements of one array smaller than the other
  • Even total length requiring an average of two middles
  • Duplicate values spanning both arrays
!

Common beginner mistakes

  • Binary-searching the longer array, letting j go negative
  • Using half = (m+n)//2 instead of (m+n+1)//2, which breaks the odd-length median
  • Omitting the infinity sentinels and crashing at the array edges
  • Returning an int instead of a float for the odd case
Check your understanding

Why must the binary search run over the smaller array?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search#74Search a 2D MatrixBinary search on a flattened grid