Median of Two Sorted Arrays

Premium

Median of Two Sorted Arrays

The median of a collection of numbers is its middle value once they are sorted — the point that splits the data into a smaller half and a larger half, or the average of the two middle values when the count is even. Here you are given two arrays that are each already sorted in ascending order, and you return the median of all of their values combined. This is the well-known "Median of Two Sorted Arrays" interview problem (LeetCode 4); the catch is the target running time. See median for background.

Signature

medianOfTwoSorted(a, b)  // a and b each sorted ascending -> number (may be a .5)

Examples

medianOfTwoSorted([1, 3], [2]);       // 2    (combined [1, 2, 3] -> middle value)
medianOfTwoSorted([1, 2], [3, 4]);    // 2.5  (combined [1, 2, 3, 4] -> average of 2 and 3)
medianOfTwoSorted([], [1, 2, 3, 4]);  // 2.5  (one array may be empty)

Notes

Both sorted — a and b are each in ascending order. You never sort them yourself.
Never both empty — at least one array holds a value, though either one alone may be empty.
Even totals average — when the combined length is even, the median is the average of the two middle values, so the result can be a .5 (a non-integer). An odd total returns the single middle value.
Values vary — numbers may be negative and may repeat across the two arrays.
Beat the merge — the interview target is O(log(min(m, n))) time, not the O(m + n) you get from merging the two arrays and indexing the middle.

FAQ

Why is the optimal solution O(log(min(m, n))) instead of O(m + n)?

Merging the two arrays reads every element, which is O(m + n). The faster approach never merges: it binary-searches the shorter array for the one cut that balances the two halves, and each step discards half of the remaining candidate cuts, so the work grows like the logarithm of the smaller length.

Why do you always binary-search the shorter array?

Once you fix how many elements of the first array go left, the count taken from the second array is forced as j = half - i. Searching the shorter array keeps j inside the longer array's bounds for every i you try, so you never read past the end of an array or drive an index negative.

How does one formula handle both even and odd totals?

Setting half = floor((m + n + 1) / 2) gives the left half the extra element when the total is odd. An odd total then reads its median straight off the left side as max(aLeft, bLeft); an even total averages the largest left value with the smallest right value.

Median of Two Sorted Arrays

Signature

medianOfTwoSorted(a, b)  // a and b each sorted ascending -> number (may be a .5)

Examples

medianOfTwoSorted([1, 3], [2]);       // 2    (combined [1, 2, 3] -> middle value)
medianOfTwoSorted([1, 2], [3, 4]);    // 2.5  (combined [1, 2, 3, 4] -> average of 2 and 3)
medianOfTwoSorted([], [1, 2, 3, 4]);  // 2.5  (one array may be empty)

Notes

Both sorted — a and b are each in ascending order. You never sort them yourself.
Never both empty — at least one array holds a value, though either one alone may be empty.
Even totals average — when the combined length is even, the median is the average of the two middle values, so the result can be a .5 (a non-integer). An odd total returns the single middle value.
Values vary — numbers may be negative and may repeat across the two arrays.
Beat the merge — the interview target is O(log(min(m, n))) time, not the O(m + n) you get from merging the two arrays and indexing the middle.

FAQ

Why is the optimal solution O(log(min(m, n))) instead of O(m + n)?

Why do you always binary-search the shorter array?

How does one formula handle both even and odd totals?

Unlock the solution & editor

Runnable editor + tests
Solve in the browser with instant Jest feedback.
Detailed solutions
Walkthroughs, edge cases, and complexity notes.
Multi-framework variants
React, Vue, Vanilla, Angular — same question, different stacks.

Upgrade to Premium