Median of two sorted lists
You get two lists of integers, nums1 and nums2, each sorted from smallest to largest. Together they hold at least one number. Return the median of all their numbers taken together, as a float: the middle number when the total count is odd, or the average of the two middle numbers when it is even. A number that appears several times counts each time.
Your solution must take O(log(m + n)) time, where m and n are the lengths of the two lists.
nums1 = [1, 5, 9], nums2 = [2, 3]Output3.0Together they are [1, 2, 3, 5, 9]. Five numbers, so the median is the third one, 3.
nums1 = [4, 6], nums2 = [1, 2, 7, 8]Output5.0Together they are [1, 2, 4, 6, 7, 8]. The two middle numbers are 4 and 6, both from nums1, and their average is 5.0.
nums1 = [], nums2 = [3, 8]Output5.5One list can be empty. The average of 3 and 8 is 5.5.
0 ≤ len(nums1), len(nums2) ≤ 105, and len(nums1) + len(nums2) ≥ 1
-106 ≤ every number ≤ 106
Both lists are sorted from smallest to largest; numbers can repeat.
O(log(m + n)) time per call.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.