Median of Two Sorted Arrays
On this page
Problem statement
Given two sorted arrays of sizes m and n, return the median of all their numbers combined, in O(log(min(m, n))) time. With an odd total the median is the middle number; with an even total it is the average of the two middle numbers. Either array may be empty, but not both.
The merge answer is easy, so the whole question is about the logarithmic bound. It is one of the best-known binary search problems because you don't search for a value: you search for a cut. Original problem: LeetCode 4.
Example

A = [1, 4, 9], B = [2, 3, 7, 10]
Output: 4.0 # merged: 1 2 3 [4] 7 9 10
A = [1, 4, 9], B = [2, 3, 7, 10, 12]
Output: 5.5 # merged: 1 2 3 [4 7] 9 10 12 -> (4 + 7) / 2
Constraints (assumed)
- 0 ≤ m, n ≤ 1,000 and m + n ≥ 1.
- Values fit in a 32-bit integer.
What this question tests
- Reframing "find the median" as "find a partition of both arrays".
- A binary search on the answer's structure, with exact conditions for moving left or right.
- Handling empty sides and odd/even totals without special-case spaghetti.
Questions to ask first
- Can either array be empty? (Here: yes, one of them.)
- Are there duplicates, and can they cross arrays? (Yes; the method doesn't care.)
- What should an even total return? The average, as a float.
- Is O(m + n) acceptable? If yes, a two-pointer merge is enough; the expected answer is logarithmic.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.