Problem
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Input: nums1 = [1,3], nums2 = [2]
Output: 2.0
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.5
Intuition
What is a median, really?
Before we touch any code, let's make sure we understand what a median actually does. The median is the "middle" value — it splits a list of numbers into two equal halves. Half the numbers are smaller, half are larger.
[1, 2, 3, 4, 5] → median = 3
^
left half: [1,2] right half: [4,5]
If the total count is even, the median is the average of the two middle numbers:
[1, 2, 3, 4] → median = (2 + 3) / 2 = 2.5
^ ^
So finding a median is really about finding where to split a collection into two equal halves.
The obvious approach (and why it's not enough)
The simplest idea: merge both sorted arrays into one big sorted array, then pick the middle element.
nums1 = [1, 3, 5]
nums2 = [2, 4, 6]
merged = [1, 2, 3, 4, 5, 6] → median = (3 + 4) / 2 = 3.5
This works perfectly and is easy to code. The problem? It takes O(m+n) time because you have to walk through every element of both arrays to merge them. The problem specifically asks for O(log(m+n)). When you see "log" in a time complexity requirement, that's a huge hint: binary search.
The key insight — think "partition," not "merge"
Here's where the magic happens. Let's reframe the problem.
We said the median splits numbers into two equal halves. What if we could find that split point without actually merging the arrays? Both arrays are already sorted, so each one is already in order. We just need to figure out how many elements from each array go into the "left half" and how many go into the "right half."
Imagine drawing a vertical line through each array:
nums1: [1, 3 | 5, 7] ← i elements on the left
nums2: [2, 4 | 6, 8] ← j elements on the left
──────┼──────
left half | right half
If we take i elements from nums1 and j elements from nums2 for the left half, then the left half has i + j elements total. For a valid median split, we need:
- Equal sizes:
i + j = half(wherehalfis half the total number of elements) - Correct ordering: everything in the left half ≤ everything in the right half
Condition 2 is the tricky part. Since each array is already sorted internally, nums1[0..i-1] are already ≤ nums1[i..m-1], and same for nums2. The only thing we need to check is the cross-array condition:
- The biggest element on the left side of
nums1must be ≤ the smallest element on the right side ofnums2 - The biggest element on the left side of
nums2must be ≤ the smallest element on the right side ofnums1
In other words:
nums1[i-1] <= nums2[j] AND nums2[j-1] <= nums1[i]
Why binary search works here
Here's the beautiful part. Once we pick i (how many elements from nums1 go into the left half), j is automatically determined: j = half - i. So we only have one variable to search over.
And the search is monotonic — if nums1[i-1] > nums2[j], we've taken too many from nums1 (move i left). If nums2[j-1] > nums1[i], we've taken too few from nums1 (move i right). That's exactly the structure binary search needs.
Why search on the shorter array?
We binary search over i from 0 to m (the length of nums1). To minimize the number of steps, we always binary search on the shorter array. If nums1 has 5 elements and nums2 has 1,000,000, we only need log2(5) ≈ 3 steps instead of log2(1,000,000) ≈ 20.
Also, searching on the shorter array guarantees that j = half - i never goes out of bounds for nums2.
Handling edge cases with -Infinity and Infinity
What if i = 0 (we take nothing from nums1 for the left half)? Then there's no nums1[i-1] to compare. We use -Infinity as a stand-in, meaning "the left side of nums1 is empty, so it can't violate any condition."
Similarly, if i = m (all of nums1 is in the left half), there's no nums1[i] on the right. We use Infinity, meaning "the right side of nums1 is empty, so it's automatically ≥ everything."
i = 0: nums1Left = -Infinity (nothing on the left, always valid)
i = m: nums1Right = Infinity (nothing on the right, always valid)
Same logic applies for j = 0 and j = n.
Odd vs. even total length
Once we find the correct partition:
Odd total (e.g., 5 elements → left half gets 3, right half gets 2): The median is the largest element in the left half.
left half: [..., nums1Left, nums2Left]
median = Math.max(nums1Left, nums2Left)
Even total (e.g., 6 elements → each half gets 3): The median is the average of the largest in the left half and the smallest in the right half.
median = (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2
The formula for half
We use half = Math.floor((m + n + 1) / 2). The +1 makes the left half one element larger when the total is odd, which simplifies our odd-case logic — we just return the max of the left side.
Total = 5: half = floor((5+1)/2) = 3 → left gets 3, right gets 2
Total = 6: half = floor((6+1)/2) = 3 → left gets 3, right gets 3
Solution
function findMedianSortedArrays(nums1, nums2) {
// Always binary search on the shorter array
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
const m = nums1.length;
const n = nums2.length;
const half = Math.floor((m + n + 1) / 2);
let left = 0;
let right = m;
while (left <= right) {
const i = Math.floor((left + right) / 2); // partition index for nums1
const j = half - i; // partition index for nums2
const nums1Left = i > 0 ? nums1[i - 1] : -Infinity;
const nums1Right = i < m ? nums1[i] : Infinity;
const nums2Left = j > 0 ? nums2[j - 1] : -Infinity;
const nums2Right = j < n ? nums2[j] : Infinity;
if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
// Found the correct partition
if ((m + n) % 2 === 1) {
return Math.max(nums1Left, nums2Left);
}
return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2;
} else if (nums1Left > nums2Right) {
// Too far right in nums1, move left
right = i - 1;
} else {
// Too far left in nums1, move right
left = i + 1;
}
}
}Line-by-line breakdown
Lines 2-4 — If nums1 is longer, swap them. We always binary search on the shorter array for efficiency and to avoid out-of-bounds on j.
Lines 6-8 — Set up sizes and calculate half, the number of elements that should be in the left half.
Lines 10-11 — Binary search bounds. i can range from 0 (take nothing from nums1) to m (take everything from nums1).
Lines 13-14 — Pick the midpoint i for nums1. Then j is forced: j = half - i.
Lines 16-19 — Get the four boundary values. These are the elements right at the partition line. Use -Infinity/Infinity for edges that don't exist.
Lines 21-26 — If the cross conditions hold, we found our answer. For odd totals, the median is the max of the left side. For even totals, average the max-left and min-right.
Lines 27-28 — nums1Left > nums2Right means we took too many from nums1. The left side of nums1 is too big, so move the partition left (decrease i).
Lines 29-30 — Otherwise, nums2Left > nums1Right means we took too few from nums1. Move the partition right (increase i).
Walking through the examples
Example 1: nums1 = [1,3], nums2 = [2]
Setup: m=2, n=1, half = floor((2+1+1)/2) = 2
Iteration 1: left=0, right=2
i = floor((0+2)/2) = 1
j = 2 - 1 = 1
nums1: [1 | 3] nums1Left = 1, nums1Right = 3
nums2: [2 | ] nums2Left = 2, nums2Right = Infinity
──┼──
left | right
[1, 2] | [3]
Check: nums1Left(1) <= nums2Right(Infinity) ✓
nums2Left(2) <= nums1Right(3) ✓ → Valid partition!
Total is odd (3), so median = Math.max(1, 2) = 2.0 ✓
Example 2: nums1 = [1,2], nums2 = [3,4]
Setup: m=2, n=2, half = floor((2+2+1)/2) = 2
Iteration 1: left=0, right=2
i = floor((0+2)/2) = 1
j = 2 - 1 = 1
nums1: [1 | 2] nums1Left = 1, nums1Right = 2
nums2: [3 | 4] nums2Left = 3, nums2Right = 4
──┼──
left | right
[1, 3] | [2, 4]
Check: nums1Left(1) <= nums2Right(4) ✓
nums2Left(3) <= nums1Right(2) ✗ → 3 > 2!
nums2Left > nums1Right → we took too few from nums1, move right
left = 1 + 1 = 2
Iteration 2: left=2, right=2
i = floor((2+2)/2) = 2
j = 2 - 2 = 0
nums1: [1, 2 | ] nums1Left = 2, nums1Right = Infinity
nums2: [ | 3, 4] nums2Left = -Infinity, nums2Right = 3
──┼──
left | right
[1, 2] | [3, 4]
Check: nums1Left(2) <= nums2Right(3) ✓
nums2Left(-Inf) <= nums1Right(Inf) ✓ → Valid partition!
Total is even (4), so median = (Math.max(2, -Inf) + Math.min(Inf, 3)) / 2
= (2 + 3) / 2
= 2.5 ✓
Example 3: nums1 = [1,2,3], nums2 = [4,5,6,7,8]
Setup: swap so nums1 is shorter → nums1 = [1,2,3], nums2 = [4,5,6,7,8]
m=3, n=5, half = floor((3+5+1)/2) = 4
Iteration 1: left=0, right=3
i = floor((0+3)/2) = 1
j = 4 - 1 = 3
nums1: [1 | 2, 3] nums1Left = 1, nums1Right = 2
nums2: [4, 5, 6 | 7, 8] nums2Left = 6, nums2Right = 7
Check: nums1Left(1) <= nums2Right(7) ✓
nums2Left(6) <= nums1Right(2) ✗ → 6 > 2!
Too few from nums1 → move right. left = 2
Iteration 2: left=2, right=3
i = floor((2+3)/2) = 2
j = 4 - 2 = 2
nums1: [1, 2 | 3] nums1Left = 2, nums1Right = 3
nums2: [4, 5 | 6, 7, 8] nums2Left = 5, nums2Right = 6
Check: nums1Left(2) <= nums2Right(6) ✓
nums2Left(5) <= nums1Right(3) ✗ → 5 > 3!
Too few from nums1 → move right. left = 3
Iteration 3: left=3, right=3
i = floor((3+3)/2) = 3
j = 4 - 3 = 1
nums1: [1, 2, 3 | ] nums1Left = 3, nums1Right = Infinity
nums2: [4 | 5, 6, 7, 8] nums2Left = 4, nums2Right = 5
Check: nums1Left(3) <= nums2Right(5) ✓
nums2Left(4) <= nums1Right(Inf) ✓ → Valid partition!
Left half: [1, 2, 3, 4] Right half: [5, 6, 7, 8]
Total is even (8), so median = (Math.max(3, 4) + Math.min(Inf, 5)) / 2
= (4 + 5) / 2
= 4.5 ✓
Merged array would be [1,2,3,4,5,6,7,8], median = (4+5)/2 = 4.5. Confirmed.
Example 4: edge case — nums1 = [], nums2 = [1]
Setup: nums1 is shorter (length 0). m=0, n=1, half = floor((0+1+1)/2) = 1
i = 0, j = 1
nums1: [ | ] nums1Left = -Infinity, nums1Right = Infinity
nums2: [1 | ] nums2Left = 1, nums2Right = Infinity
Check: -Infinity <= Infinity ✓
1 <= Infinity ✓ → Valid!
Odd total → median = Math.max(-Infinity, 1) = 1 ✓
The -Infinity/Infinity sentinel values handle empty arrays gracefully.
Visualizing the search
Think of it like a slider on nums1. You're sliding the partition point from left to right:
i=0: [ | 1, 3, 5] j=3: [2, 4, 6 | ] too few from nums1?
i=1: [1 | 3, 5] j=2: [2, 4 | 6] just right?
i=2: [1, 3 | 5] j=1: [2 | 4, 6] too many from nums1?
i=3: [1, 3, 5 | ] j=0: [ | 2, 4, 6] too many from nums1?
Binary search finds the sweet spot in O(log m) steps instead of checking every position.
Complexity
- Time: O(log(min(m, n))) — binary search on the shorter array
- Space: O(1) — only using a few pointer variables
Common mistakes
-
Not swapping to the shorter array — If you binary search on the longer array,
j = half - imight go negative, causing out-of-bounds errors. -
Getting the
halfformula wrong — Using(m + n) / 2instead of(m + n + 1) / 2mishandles odd-length totals. The+1ensures the left half is one larger for odd totals. -
Forgetting sentinel values — Without
-Infinity/Infinityat the boundaries, you need extra if-statements for wheni=0,i=m,j=0, orj=n. The sentinels make the code cleaner. -
Confusing
iandi-1—iis the number of elements fromnums1in the left half.nums1[i-1]is the last element in the left half, andnums1[i]is the first element in the right half.
Key Takeaway
When you need to find a positional element (like a median) across two sorted arrays, think partition instead of merge. You don't need to combine the arrays — you just need to find the right cut point. Binary searching on the shorter array to find where to split gives you logarithmic time. The core idea is that once you choose how many elements from one array go into the left half, the other array's split is fully determined.