110. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).

Input: Two sorted integer arrays nums1 and nums2.

Output: Float — median of the merged sorted array (to 5 decimal places).

Examples

Input: [1,3],[2]
Output: 2.00000
Explanation: Merged: [1,2,3]. Median=2.

Input: [1,2],[3,4]
Output: 2.50000
Explanation: Merged: [1,2,3,4]. Median=(2+3)/2=2.5.

Input: [0,0],[0,0]
Output: 0.00000
Explanation: Merged: [0,0,0,0]. Median=0.

Constraints

• 0<=m,n<=1000
• 1<=m+n<=2000
• -10^6<=nums1[i],nums2[i]<=10^6

Asked by