You are given two integer arrays nums1 and nums2, each sorted from smallest to largest. Return the median of all their values taken together.
The median is the middle value once every value from both arrays is lined up in sorted order. When the total count is even there are two middle values, and the median is their average, so it can end in .5.
Merging the two arrays and reading off the middle runs in O(m + n) time and is accepted at these sizes. The real challenge is to find the median in O(log(min(m, n))) time, without merging.
There are five values in all, so the median is the third smallest, 5.
Together the values are [1,2,3,6,9,10]. The two middle values are 3 and 6, and their average is 4.5.
One array can be empty. The median of -4 and 8 is (-4 + 8) / 2 = 2.
Constraints
nums1.length == m and nums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10⁶ <= nums1[i], nums2[i] <= 10⁶nums1 and nums2 are each sorted in non-decreasing order.10⁻⁵ of the true median is accepted.The median splits all m + n values into a left half and a right half of equal size (the left gets the extra one when the total is odd). Choosing how many values the left half takes from the shorter array fixes how many it takes from the longer one, so there is only one number to search for.
The median is about position, not value: with m + n values lined up in order, it's the one in the middle, or the average of the two middle ones. So the plain plan is to line them up and look. Both arrays are already sorted, so lining them up is a merge, and you can stop halfway. That's O(m + n), and at these sizes it's accepted.
Time O(log(min(m, n)))Space O(1)
The full walkthrough and code are part of Premium
5.00000