LeetCode 4 ·
Hard
Median of Two Sorted Arrays
Return the median of two sorted arrays in logarithmic time.
Try it
Step through the core mechanic. The simulator below runs the binary search shape this problem is built on.
Interactive · Binary search walkthrough Sorted array; halve the search range at each step.
0
-7
L
1
-3
2
0
3
2
4
5
5
8
6
11
7
14
8
17
9
21
10
25
11
30
H
start: lo=0, hi=11, mid=5, a[mid]=8
range12 log₂(n)≤ 4 step0 / 3
Why binary search is O(log n).
Each step halves the search range. Starting from
n, after
k steps the range is n / 2ᵏ; the search ends when
this drops below 1, so k ≤ log₂(n). For n = 10⁹,
that's ≤ 30 steps. The interview corollary: if the constraint is
n ≤ 10⁹, you need an O(log n) approach — binary search is
usually the one.The approach
Binary search the partition point of the smaller array so that left halves hold (m+n+1)/2 elements and every left element ≤ every right element. The median falls out of the four boundary values.
| Aspect | Value |
|---|---|
| Pattern | Binary search |
| Recognise it by | Median of two sorted arrays in O(log(m+n)). |
| Time complexity | O(log min(m,n)) |
| Space complexity | O(1) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.