Median of Two Sorted Arrays

This problem requires you to find the median of two sorted arrays. The median is defined as the middle value of a sorted list of numbers. If the total number of elements is even, the median is calculated as the average of the two middle numbers. Formally, if the merged sorted array is \(A\) with \(N\) elements, then the median is given by:

\( \text{median} = \begin{cases} A[(N+1)/2] & \text{if } N \text{ is odd}, \\ \frac{A[N/2] + A[N/2+1]}{2} & \text{if } N \text{ is even}. \end{cases} \)

An efficient solution with a time complexity of \(O(\log(m+n))\) using a binary search technique is expected.

inputFormat

The input consists of two lines:

• The first line contains \(m\) space-separated integers representing the first sorted array. It can be empty, indicating an empty array.
• The second line contains \(n\) space-separated integers representing the second sorted array. It can also be empty.

You may assume that both arrays are sorted in non-decreasing order.

outputFormat

Output a single floating point number which is the median of the two sorted arrays. Even if the median is an integer, it should be output in floating-point format (e.g., 2.0).

1 3
2

2.0