Problem
Both lists are sorted in ascending order. Find the median of all their numbers together; for an even count it is the average of the two middle values. An O(log(m + n)) partition search is possible, but any correct method within the limits is accepted.
Implement median_of_two(first, second).
Input
first: A sorted list. second: A sorted list.
Output
Return the median.
Constraints
0 ≤ lengths ≤ 100,000; the combined length is at least 1
Examples
Input:
first = [1, 3]
second = [2]
Expected output:
expected = 2.0Input:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};
Expected output:
double expected = 2.0;Input:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};
Expected output:
double expected = 2.0;Explanation
Combined: [1, 2, 3]; the middle value is 2.
Input:
first = [1, 2]
second = [3, 4]
Expected output:
expected = 2.5Input:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Expected output:
double expected = 2.5;Input:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Expected output:
double expected = 2.5;Explanation
Combined: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
The combined order matters, but you do not need to merge everything if you can find the middle split directly.
Hint 2
Search for a partition where left halves contain exactly the lower middle elements and every left value is no larger than every right value.
Hint 3
Handle empty arrays and both odd and even total lengths carefully, since the median may come from one middle value or two.
Expected complexity
O(log(min(m, n))) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.