Median of Two Sorted Arrays

Hard

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)).

The median of an array of length L is the (L/2)-th element if L is odd, or the average of the (L/2-1)-th and (L/2)-th elements if L is even (0-indexed, integer division). For this problem, return the integer part (floor) of the median.

Example 1

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

Example 2

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

Constraints

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