Median of Two Sorted Arrays

You are given two sorted arrays. Your task is to find the median of the two sorted arrays combined. The overall run time complexity of your solution should be \(O(\log(\min(m,n)))\), where \(m\) and \(n\) are the lengths of the two arrays respectively.

The median is defined as the middle value in an ordered integer list. If the total number of elements is even, the median is the average of the two middle numbers. More formally, if the two arrays are denoted by \(A\) and \(B\) and merged to form a sorted array \(C\), then:

• If \(|C|\) is odd, \(median = C[(|C|+1)/2]\).
• If \(|C|\) is even, \(median = \frac{C[|C|/2] + C[|C|/2 + 1]}{2}\).

Note: One or both arrays may be empty. It is guaranteed that at least one of the arrays is non-empty. All arrays are already sorted in non-decreasing order.

inputFormat

The input is read from standard input and consists of four lines:

1. The first line contains an integer \(m\), the number of elements in the first array.
2. The second line contains \(m\) space-separated integers representing the first sorted array. If \(m = 0\), this line will be empty.
3. The third line contains an integer \(n\), the number of elements in the second array.
4. The fourth line contains \(n\) space-separated integers representing the second sorted array. If \(n = 0\), this line will be empty.

outputFormat

Print the median as a floating-point number to standard output.

2
1 3
1
2

2.0