Median of Two Sorted Arrays

Difficulty: Hard · Topic: Searching

Given two sorted ascending arrays a and b, return the median of the combined set of numbers as a float. If the total count is even, the median is the average of the two middle values.

A clean O(m+n) merge earns the green check; the famous O(log(m+n)) binary-search-on-partition is the stretch goal.

Examples

find_median_sorted([1,3], [2])
→ 2

Merged [1,2,3] → median 2.

find_median_sorted([1,2], [3,4])
→ 2.5

Merged [1,2,3,4] → (2+3)/2.

Target complexity: time O(m + n), space O(m + n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.