Median of Two Sorted Arrays

You are given two sorted arrays (which may be empty). Your task is to compute the median of the union of these two arrays. The median is defined as the middle element when the arrays are combined and sorted. If the total number of elements is even, the median is the average of the two middle numbers.

More formally, let \(A\) and \(B\) be two sorted arrays. You need to find the median of \(A \cup B\). For an odd-length union, the median is the middle element; for an even-length union, it is given by \[ \text{median} = \frac{a_{\frac{n}{2}-1}+a_{\frac{n}{2}}}{2} \] where \(n\) is the total number of elements and \(a_i\) denotes the \(i^{th}\) element (0-indexed) of the sorted union.

inputFormat

The input consists of two lines read from standard input:

• 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. If the array is empty, the line will be empty.

Note: Both arrays are already sorted in ascending order.

outputFormat

Output a single number to standard output, representing the median of the combined sorted arrays. If the median is a fractional number, output it in decimal form.

1 3 5 7 9
2 4 6 8

5