Median of Two Sorted Arrays

Table of Contents +

Median of Two Sorted Arrays scares people. It is marked hard, and the fast solution uses binary search in a way most people have never seen. But the idea behind it is clean once you slow down. The interviewer wants to see if you can find a clever cut instead of just merging everything.

🎯 The Problem

You get two sorted arrays and want the median of all their numbers combined. The rules:

  • Both arrays are already sorted.
  • The median is the middle value once every number is lined up in order.
  • If the total count is odd, the median is the single middle number.
  • If the total count is even, the median is the average of the two middle numbers.
  • Aim for better than fully merging both arrays.
Input:  nums1 = [1, 3], nums2 = [2]
Output: 2.0


Explanation: Combined sorted = [1, 2, 3], middle value is 2.


Input:  nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5


Explanation: Combined sorted = [1, 2, 3, 4], middle two are 2 and 3, average is 2.5.

Here is the picture. Two sorted arrays go in. We want the middle of the merged result without building the whole merge.

nums1 = [1, 3]

combine in sorted order

nums2 = [2]

[1, 2, 3]

median = middle = 2.0

🐢 Approach 1: Merge Then Pick the Middle (Brute Force)

Build the full merged sorted array, then read its middle.

The idea:

  • Both arrays are sorted.
  • Walk through them together, like a zip.
  • Build one merged sorted array.
  • The median is the middle of that merged array.

How it works:

  • Compare the front of each array. Take the smaller. Repeat.
  • This gives one fully sorted list.
  • Pick the single middle, or average the two middles.

Why it is weak:

  • It builds the entire merged list just to read one middle value.
  • Time is O(m + n) and space is O(m + n), where m and n are the array sizes.
  • We do not need the whole merge, only the middle.

Here is the merge-then-pick code:

median_two_sorted_arrays_merge.py
def find_median_sorted_arrays(nums1, nums2):
    merged = sorted(nums1 + nums2)
    n = len(merged)
    mid = n // 2
    if n % 2 == 1:
        return merged[mid]
    return (merged[mid - 1] + merged[mid]) / 2

⚡ Approach 2: Binary Search the Partition (Best)

Find the cut that splits all numbers into equal halves, without merging.

The idea:

  • The median splits the combined numbers into two equal halves.
  • The left half holds the smaller numbers. The right half holds the larger numbers.
  • So hunt for the right partition. A partition is a cut that decides how many numbers from each array go left.

How it works:

  • Always binary search the smaller array. Call its size m.
  • Pick i, how many of its numbers go left. Then j for the bigger array is fixed, since both halves hold the same count.
  • Look at the four border numbers: left1 and right1 from the first array, left2 and right2 from the second.
  • The cut is correct when left1 <= right2 and left2 <= right1.
  • If left1 is too big, you took too many, so move the cut left.
  • If left2 is too big, you took too few, so move the cut right.

Why it is fast:

  • Each step halves the cut range.
  • Time is O(log(min(m, n))).
  • It never merges, so space is O(1).

Here is a dry run on nums1 = [1, 3] and nums2 = [2]. Watch the cut range narrow.

search cut in [1, 3], range i in 0..2

i = 1: left1=1, right1=3, left2=2, right2=inf

check 1 <= inf and 2 <= 3, both true

cut is correct

max left = max(1, -inf) = 1... wait total odd

median = min(right1, right2) = min(3, 2) = 2.0

Steps to Solve

  1. Make sure you binary search the smaller array. If the first array is bigger, swap them.
  2. Set the search range for the cut i from 0 to the size of the smaller array.
  3. Pick the middle cut i. The cut j in the other array is fixed by the half-size rule.
  4. Find the four border numbers around both cuts. Use minus infinity on the far left and plus infinity on the far right when a cut sits at an edge.
  5. If left1 <= right2 and left2 <= right1, the cut is correct. Compute the median from the border numbers.
  6. If left1 > right2, move the cut left. If left2 > right1, move the cut right. Repeat.

This Python version binary searches a cut in the smaller list and uses infinity for the edges.

median.py
def find_median(a, b):
    if len(a) > len(b):        # always search the smaller array
        a, b = b, a
    m, n = len(a), len(b)
    lo, hi, half = 0, m, (m + n + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2          # cut in the smaller array
        j = half - i                # cut in the bigger array
        left1 = float("-inf") if i == 0 else a[i - 1]
        right1 = float("inf") if i == m else a[i]
        left2 = float("-inf") if j == 0 else b[j - 1]
        right2 = float("inf") if j == n else b[j]
        if left1 <= right2 and left2 <= right1:   # correct cut
            if (m + n) % 2 == 1:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            hi = i - 1              # took too many, move left
        else:
            lo = i + 1              # took too few, move right




print(find_median([1, 3], [2]))
print(find_median([1, 2], [3, 4]))

The output of the above code will be:

2.0
2.5

Let us read the Python version line by line, since the cut logic is the heart of it.

def find_median(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    lo, hi, half = 0, m, (m + n + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        left1 = float("-inf") if i == 0 else a[i - 1]
        right1 = float("inf") if i == m else a[i]
        left2 = float("-inf") if j == 0 else b[j - 1]
        right2 = float("inf") if j == n else b[j]
        if left1 <= right2 and left2 <= right1:
            if (m + n) % 2 == 1:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            hi = i - 1
        else:
            lo = i + 1

if len(a) > len(b): a, b = b, a swaps so that a is the smaller array. We binary search a, so a smaller a means fewer steps and a clean range.

lo, hi, half = 0, m, (m + n + 1) // 2 sets the cut range from 0 to m, and half is how many numbers the left side must hold. The + 1 makes odd totals put the extra number on the left, which is what we want for the median.

i = (lo + hi) // 2 picks the middle cut in a. j = half - i is forced, because the two cuts together must give exactly half numbers on the left.

The four border lines pick left1, right1, left2, right2. When a cut sits at the very start, there is no number to its left, so we use minus infinity. When it sits at the very end, there is no number to its right, so we use plus infinity. These sentinels let the comparisons just work without special edge code.

if left1 <= right2 and left2 <= right1 is the correctness check. It says every number on the left is not bigger than every number on the right. When this holds, the cut is the median cut.

If the total count is odd, the median is the biggest number on the left, which is max(left1, left2). If it is even, the median is the average of the biggest left and the smallest right.

elif left1 > right2: hi = i - 1 means a gave too many numbers to the left, so we slide the cut left. The else: lo = i + 1 means a gave too few, so we slide it right. That sliding is the binary search.

⏱️ Time and Space Complexity

The merge approach is simple but builds the whole merged array, so it is O(m + n) time and O(m + n) space. The partition approach never merges. It binary searches only the smaller array, so it is O(log(min(m, n))) time and O(1) extra space. The win is going from linear time down to logarithmic time.

Approach Time Complexity Space Complexity
Merge then pick middle O(m + n) O(m + n)
Binary search partition O(log(min(m, n))) O(1)

Tip

Always binary search the smaller array. That keeps the cut range small and avoids index mistakes. If you forget the swap, the cut j can go negative and the code breaks.

🧩 Key Takeaways

  • ✅ The median splits all numbers into a left half and a right half of equal size.
  • ✅ Instead of merging, find the cut where every left number is not bigger than every right number.
  • ✅ Binary search the smaller array to pick how many of its numbers go left.
  • ✅ Use minus and plus infinity at the edges so border checks need no special cases.
  • ✅ This runs in O(log(min(m, n))) time and uses no extra array.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What is the time complexity of the simple merge approach?

    Why: Merging both sorted arrays touches every element once, so it is O(m + n) time and O(m + n) space.

  2. 2

    Which array does the optimal solution binary search?

    Why: We always binary search the smaller array, which keeps the cut range small and gives O(log(min(m, n))).

  3. 3

    When is a cut correct?

    Why: A cut is correct when every number on the left is not bigger than every number on the right, which is exactly left1 <= right2 and left2 <= right1.

  4. 4

    Why do we use minus and plus infinity at the edges?

    Why: When a cut sits at an edge there is no neighbor, so infinity sentinels let the comparisons pass cleanly without extra cases.

Score: 0 / 4

🚀 What’s Next?

Previous Time Based Key-Value Store Next Split Array Largest Sum