Find Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of sizes \(m\) and \(n\) respectively, your task is to find the median of the combined sorted array. The median is defined as:

\[ median = \begin{cases} \max(\text{left}) & \text{if } (m+n) \text{ is odd}, \\ \frac{\max(\text{left})+\min(\text{right})}{2} & \text{if } (m+n) \text{ is even} \end{cases} \]

You are required to implement an efficient solution with an expected time complexity of \(O(\log(\min(m, n)))\). Note that one of the arrays might be empty but not both simultaneously.

inputFormat

The input is read from stdin and consists of three lines:

1. The first line contains two integers \(m\) and \(n\), representing the sizes of the two arrays.
2. The second line contains \(m\) space-separated integers (if \(m > 0\)); otherwise, it will be empty.
3. The third line contains \(n\) space-separated integers (if \(n > 0\)); otherwise, it will be empty.

outputFormat

Output a single line to stdout which contains the median value printed with 6 decimal places.

4 4
1 3 8 9
2 4 7 10

5.500000