Median of Two Sorted Arrays

Given two sorted arrays, find the median of the two sorted arrays. The overall run-time complexity should be \(O(\log(\min(m,n))\) where \(m\) and \(n\) are the sizes of the two arrays.

The median is defined as follows:

• If the total number of elements is odd, the median is the middle element.
• If the total number of elements is even, the median is the average of the two middle elements.

Arrays may be empty. However, it is guaranteed that the combined non-empty arrays will allow a valid median calculation.

inputFormat

The input is provided via standard input (stdin) and consists of four lines:

1. The first line contains an integer \(m\) — the number of elements in the first sorted 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 sorted array.
4. The fourth line contains \(n\) space-separated integers representing the second sorted array. If \(n = 0\), this line will be empty.

outputFormat

Output the median as a floating point number to standard output (stdout). If the median is an integer, it should still be printed in a floating format (e.g., 2.0).

2
1 3
1
2

2.0