Median of Two Sorted Arrays

Q: Why binary search over the shorter array?

The partition index i ranges over 0..m. Searching the shorter list keeps the run time at O(log(min(m, n))), and it guarantees j = half - i stays within 0..n, so you never index outside the longer list.

Q: Why does half use (m + n + 1) // 2?

The + 1 puts the extra element on the left side when the total is odd. Then the median of an odd total is simply max(Aleft, Bleft), and the even case uses both sides. Either convention works if you read the answer from the matching side.

hardHard arrays and strings

You get two lists of integers, nums1 and nums2, each already sorted in ascending order. One of them may be empty, but not both. Return the median of all the values together, as a float: the middle value if the combined count is odd, or the average of the two middle values if it is even.

Merging solves it in linear time. The intended solution runs in O(log(min(m, n))) without merging, by binary searching for where to cut the two lists.

Examples

Example 1

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

Output: 3.0

Explanation: Together they are 1, 2, 3, 4, 9, so the middle value is 3.

Example 2

Input: nums1 = [10,20], nums2 = [5,15,25,35]

Output: 17.5

Explanation: Together: 5, 10, 15, 20, 25, 35. The middle pair is 15 and 20.

Hints

Approach

Binary search the partition. Make A the shorter list. We want to take i elements from A and j = half - i from B, where half = (m + n + 1) // 2, so that the left side holds the smaller half of all values.

With Aleft = A[i-1], Aright = A[i], Bleft = B[j-1], Bright = B[j] (using minus or plus infinity past the ends), the split is correct when Aleft <= Bright and Bleft <= Aright.

If Aleft > Bright, too much was taken from A: move hi = i - 1.
If Bleft > Aright, too little: move lo = i + 1.

At the correct split, the median is max(Aleft, Bleft) for an odd total, or the average of that and min(Aright, Bright) for an even total. The search runs over the shorter list only.

ComplexityTime O(log(min(m, n)))Space O(1)

Python

def find_median_sorted_arrays(nums1, nums2):
    a, b = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1)
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    INF = float("inf")
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        a_left = a[i - 1] if i > 0 else -INF
        a_right = a[i] if i < m else INF
        b_left = b[j - 1] if j > 0 else -INF
        b_right = b[j] if j < n else INF
        if a_left > b_right:
            hi = i - 1
        elif b_left > a_right:
            lo = i + 1
        else:
            left = max(a_left, b_left)
            if (m + n) % 2:
                return float(left)
            return (left + min(a_right, b_right)) / 2
    raise ValueError("inputs must be sorted")
 
 
print(find_median_sorted_arrays([1, 4, 9], [2, 3]))
print(find_median_sorted_arrays([10, 20], [5, 15, 25, 35]))

Follow-up questions

Find the k-th smallest element of the two sorted lists (the same partition idea, or discard k/2 elements per step).
What about the median across k sorted lists held on different machines?

Frequently asked questions

Combining sorted data from several sources without re-sorting is common in infra: merging sorted log segments or computing a percentile across shards that each keep their own sorted samples. The problem itself is a well-known hard binary-search question in SWE-style loops, and it checks careful boundary handling more than any single idea.

The partition index i ranges over 0..m. Searching the shorter list keeps the run time at O(log(min(m, n))), and it guarantees j = half - i stays within 0..n, so you never index outside the longer list.

The + 1 puts the extra element on the left side when the total is odd. Then the median of an odd total is simply max(Aleft, Bleft), and the even case uses both sides. Either convention works if you read the answer from the matching side.

Problem statement