Median of Two Sorted Arrays

Given two sorted arrays, the task is to find the median of the combined sorted array. The median is defined as follows: if the total number of elements (n) is odd, the median is the element at position (\frac{n+1}{2}); if (n) is even, it is the average of the two middle elements, i.e. (\frac{a_{\frac{n}{2}} + a_{\frac{n}{2}+1}}{2}). The overall run-time complexity should ideally be (O(\log(m+n))), where (m) and (n) are the sizes of the two arrays. It is guaranteed that the arrays are sorted in non-decreasing order and may include duplicate values or even be empty.

inputFormat

The input is given via standard input (stdin) in two lines. The first line contains the elements of the first sorted array separated by spaces (if the array is empty, the line will be empty). The second line contains the elements of the second sorted array separated by spaces (or empty if the array is empty).

outputFormat

Output the median value as a floating point number to standard output (stdout).## sample

1 3
2

2.0