AlgoMaster Logo

Median of Two Sorted Arrays

hard10 min readUpdated June 23, 2026

Understanding the Problem

We have two arrays, both already sorted in ascending order, and we need to find the median of their combined elements. The median is the middle value when all elements are arranged in order. If the total number of elements is even, the median is the average of the two middle values.

One approach is to merge the two arrays and pick the middle element, which takes O(m + n) time. The problem asks for O(log(m + n)), which points toward binary search.

Finding the median comes down to finding the correct partition point. If we split the combined elements into a left half and a right half of equal size, where every element in the left half is less than or equal to every element in the right half, then the median comes directly from the elements at the partition boundary. Binary search finds this partition in logarithmic time without merging anything.

Key Constraints:

  • 0 <= m <= 1000 and 0 <= n <= 1000 -- Either array can be empty. We need to handle the case where one array contributes nothing to the partition.
  • 1 <= m + n <= 2000 -- The combined size is at most 2000. Even an O(m + n) merge would be fast enough in practice, but the problem demands O(log(m + n)).
  • -10^6 <= nums1[i], nums2[i] <= 10^6 -- Values fit in a standard integer. No overflow concerns when summing two elements for the average.

Approach 1: Merge and Find Middle

Intuition

Since both arrays are sorted, we can merge them into one sorted array using the two-pointer merge technique (the same merge step from merge sort). Once merged, the median is the middle element, or the average of the two middle elements for an even total length.

This does not meet the O(log(m+n)) requirement, but it is a correct baseline that frames the rest of the solutions.

Algorithm

  1. Create a merged array of size m + n.
  2. Use two pointers i and j, starting at the beginning of nums1 and nums2.
  3. Compare nums1[i] and nums2[j]. Place the smaller value into the merged array and advance that pointer.
  4. When one array is exhausted, copy the remaining elements from the other.
  5. If the total length is odd, return the middle element. If even, return the average of the two middle elements.

Example Walkthrough

1Start: i=0 on nums1=[1,3], j=0 on nums2=[2], merged=[]
1/5

Code

This approach builds the entire merged array even though only the middle element or two are needed. The next approach reaches the median position by counting, without storing anything.

Approach 2: Two Pointer Count (No Full Merge)

Intuition

We do not need the full merged array. Advancing through both arrays in sorted order until we reach the median position is enough. By counting steps with two pointers, we find the middle element or two in O(m + n) time with O(1) space.

Use two pointers on nums1 and nums2, always advancing the one pointing at the smaller value (the same logic as merging, but without storing anything). Count how many steps have been taken. The values at and just before the median position are the ones we need.

Algorithm

  1. Calculate half = (m + n) / 2.
  2. Use two pointers i and j starting at 0 on nums1 and nums2.
  3. Advance the pointer with the smaller current value, counting each step.
  4. Track the current and previous values as you go.
  5. After half + 1 steps, if the total is odd, return the current value. If even, return the average of current and previous.

Example Walkthrough

1Start: total=4, half=2, i=0, j=0, prev=0, curr=0
0
1
i
1
2
1/5

Code

The counting approach removes the extra space but still runs in linear time. Because both arrays are sorted, binary search can locate the correct partition directly instead of stepping to it one element at a time.

Approach 3: Binary Search on Partition

Intuition

The median splits all m + n elements into two equal halves. If we know how many elements to take from nums1 for the left half, the rest must come from nums2. Finding the median reduces to finding the right number of elements to take from one array, and that count can be found with binary search in O(log(min(m, n))).

Take i elements from nums1 and j elements from nums2 for the left half, where i + j = (m + n + 1) / 2. The partition is valid when:

  • The largest element from nums1's left part (nums1[i-1]) is less than or equal to the smallest element from nums2's right part (nums2[j]).
  • The largest element from nums2's left part (nums2[j-1]) is less than or equal to the smallest element from nums1's right part (nums1[i]).

We always binary search on the smaller array to keep the search range minimal and avoid out-of-bounds issues.

Algorithm

  1. Ensure nums1 is the smaller array. If not, swap them.
  2. Set left = 0, right = m (the length of the smaller array).
  3. Compute half = (m + n + 1) / 2.
  4. While left <= right:
    • Set i = (left + right) / 2 (elements from nums1 in the left half).
    • Set j = half - i (elements from nums2 in the left half).
    • Compute the four boundary values: maxLeft1, minRight1, maxLeft2, minRight2. Use -infinity and +infinity for out-of-bounds.
    • If maxLeft1 > minRight2: we took too many from nums1, search left (right = i - 1).
    • Else if maxLeft2 > minRight1: we took too few from nums1, search right (left = i + 1).
    • Else: valid partition found. The median depends on odd/even total.
  5. For odd total: max(maxLeft1, maxLeft2). For even total: average of max(maxLeft1, maxLeft2) and min(minRight1, minRight2).

Example Walkthrough

1Setup: nums1=[1,3], nums2=[2,7,9], total=5 (odd), half=3, left=0, right=2
0
1
1
3
search range
1/8

Code

Approach 4: Binary Search on the Value

Intuition

The partition approach binary searches over an index. A different technique binary searches over the answer value itself. The median is the k-th smallest combined element (or the average of two consecutive k-th smallest elements), so the problem reduces to finding the k-th smallest value across two sorted arrays.

For a candidate value v, the number of combined elements that are less than or equal to v is countLessEqual(nums1, v) + countLessEqual(nums2, v), and each count is itself a binary search inside one sorted array. That total count is non-decreasing as v increases, so we can binary search the value range for the smallest v whose count reaches k. That smallest v is the k-th smallest element.

This is the more general technique. It extends directly to finding the k-th smallest element across any number of sorted arrays, where the partition method does not generalize as cleanly.

Algorithm

  1. Define kthSmallest(k) as the smallest value v such that at least k combined elements are less than or equal to v.
  2. Binary search v over the value range [-10^6, 10^6]. For each candidate mid, count elements <= mid in both arrays using a binary search in each.
  3. If the count is at least k, the answer is mid or smaller, so move hi = mid. Otherwise move lo = mid + 1.
  4. For an odd total, return kthSmallest((m + n) / 2 + 1).
  5. For an even total, return the average of kthSmallest((m + n) / 2) and kthSmallest((m + n) / 2 + 1).

Example Walkthrough

For nums1 = [1, 3] and nums2 = [2], the total is 3 (odd), so the median is the 2nd smallest value, kthSmallest(2). The combined sorted order is 1, 2, 3, so the answer is 2. The value search below is shown narrowed to the data range [1, 3]; the code searches the full range [-10^6, 10^6], which takes a fixed number of iterations regardless of input.

1Find kthSmallest(2). Value search range lo=1, hi=3
0
1
1
3
value range
1/7

Code

The partition approach (Approach 3) is the one that meets the required O(log(m + n)) bound with O(1) space. The value search trades a tighter bound for a technique that generalizes to k sorted arrays.