Median of Two Sorted Arrays
A hard Binary Search interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Binary Search
- Sheets
- 2
- Core for
- 7 roles
The problem
Two arrays nums1 and nums2 are each sorted. Treat them as if they were merged into one sorted list and return the median of that list, without building it: the intended solution runs in O(log(m+n)) time, where m and n are the two lengths.
Example 1
- Input
- nums1 = [2,4], nums2 = [3,5,6]
- Output
- 4.0
- Why
- Merged: [2,3,4,5,6], median is 4.0.
Example 2
- Input
- nums1 = [1,3,5], nums2 = [2,4,6,8]
- Output
- 4.0
- Why
- Merged: [1,2,3,4,5,6,8], median is 4.0.
Constraints
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
How to think about it
Updated 2026-09-29The median divides a combined collection into two equal halves where all left elements are smaller than all right elements. Once you choose how many items from the smaller array belong in the left half, the count needed from the second array is completely fixed.
Approaches, worst first
Merge arrays
time O(m + n) · space O(m + n)
Merge both sorted arrays with two pointers into an auxiliary array of size m + n and take the middle element. Straightforward to write, but creates unnecessary storage and scans every element linearly.
Two-pointer step counting
time O(m + n) · space O(1)
Advance through both arrays in sorted order without allocating full storage until reaching the (m + n) / 2 mark. Drops extra memory, but still visits items linearly.
Binary search on shorter array partitionWrite this one
time O(log(min(m, n))) · space O(1)
Binary search on the partition cut index of the shorter array. The partition cut of the second array is derived algebraically, and a valid split is confirmed when cross-boundary elements satisfy sorted order.
Where people lose marks · 3
- Binary searching the longer array allows the derived partition index in the shorter array to fall out of bounds; always enforce nums1 as the shorter array.
- Partition cuts landing at index 0 or array length require using -infinity and +infinity guards to prevent reading out-of-bounds memory.
- Integer division when combining the two central elements for an even total length drops the fractional half; cast sums to floating point before dividing by 2.
The theory behind it
Binary Search — the ground this problem stands on. All Binary Search problems
What Binary Search is
Binary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How the pattern works
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
More Binary Search problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .