AlgoMaster Logo

Median of Two Sorted Arrays

Last Updated: March 29, 2026

hard
5 min read

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.

The straightforward approach would be to merge the two arrays and pick the middle element. That's O(m + n) time. But the problem explicitly asks for O(log(m + n)), which is a strong hint that we need binary search.

The key observation is this: finding the median is really about finding the correct partition point. If we can 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 lets us find this partition in logarithmic time without actually 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

The most natural approach: since both arrays are sorted, merge them into one sorted array using the two-pointer merge technique (the same merge step from merge sort). Once merged, the median is just the middle element (or the average of the two middle elements for even-length arrays).

This doesn't meet the O(log(m+n)) requirement, but it's an important starting point. It verifies your understanding of the problem and gives you a correct baseline to compare against.

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 works correctly but merges the entire arrays even though we only need the middle element(s). What if we counted our way to the median position without storing the full merge?

Approach 2: Two Pointer Count (No Full Merge)

Intuition

We don't actually need the full merged array. We just need to advance through both arrays in sorted order until we reach the median position. By counting steps with two pointers, we can find the middle element(s) in O(m + n) time with O(1) space.

The idea is simple: use two pointers on nums1 and nums2, always advancing the one pointing at the smaller value (same logic as merging, but without storing anything). Count how many steps we've taken. When we reach the median position, record that value.

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 eliminates extra space but is still linear. Since both arrays are sorted, can we binary search for the correct partition instead of walking to it one element at a time?

Approach 3: Binary Search on Partition

Intuition

Here's the core insight that makes O(log(min(m, n))) possible. 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. So finding the median reduces to finding the right number of elements to take from one array.

Let's say we 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,2], nums2=[3,4], half=2, left=0, right=2
0
1
1
2
search range
1/6

Code