#21HardBinary Search & Divide and Conquer· Binary Search on a Partition

Median of Two Sorted Arrays

You are given two arrays `nums1` (length `m`) and `nums2` (length `n`), each sorted in non-decreasing order. Return the **median** of all `m + n` values taken together. The median of an odd number of values is the middle value after sorting; for an even number it is the average of the two middle values. One of the arrays may be empty, but not both. Your algorithm must run in `O(log(m + n))` time, so merging the arrays is not acceptable. The output is printed with exactly five digits after the decimal point.

Input format

nums1: sorted array of integers (may be empty), nums2: sorted array of integers (may be empty)

Output format

Floating-point number formatted with five decimal places, e.g. `2.50000`

Examples

Input: nums1 = [1, 3], nums2 = [2]

Output: 2.00000

All values together are [1, 2, 3]; the middle value is 2.

Input: nums1 = [1, 2], nums2 = [3, 4]

Output: 2.50000

All values together are [1, 2, 3, 4]; the median is (2 + 3) / 2 = 2.5.

Input: nums1 = [], nums2 = [1]

Output: 1.00000

One array may be empty.

Constraints

0 <= m, n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
Both arrays are sorted in non-decreasing order.

Study first

#binary-search
#divide-and-conquer
#arrays