Binary Search Partition search
259. Median of Two Sorted Arrays
You are given two arrays of integers, first and second, each sorted from smallest to largest. Return the
median of all their values taken together.
The median of a list of values is its middle value once the list is sorted. When the list holds an even number of values, it has two middle values, and the median is their average, which can end in .5. Equal values count separately, so the median of 1, 2, 2 and 9 is 2.
Either array can be empty, but not both. The answer is shown with at least one digit after the decimal point,
so a median of 4 shows as 4.0.
Aim for O(log(m + n)) time, where m and n are the lengths of first and second.
Example 1
Input: first = [3, 8, 9, 15], second = [1, 6, 7, 20]
7.5Explanation: Together the arrays hold 1, 3, 6, 7, 8, 9, 15 and 20. That is eight values, so the median is the average of the 4th and the 5th, (7 + 8) / 2 = 7.5.
Example 2
Input: first = [4, 4, 6], second = [1, 4, 8, 9]
4.0Explanation: Together the arrays hold 1, 4, 4, 4, 6, 8 and 9, and the 4th of these seven values is 4. The three 4s count as
three values: two come from first and one from second.
Example 3
Input: first = [], second = [-8, -5, -2, 4]
-3.5Explanation: first is empty, so the median is the median of second alone. Its middle values are −5 and −2, and their
average is −3.5.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ first.length ≤ 1050 ≤ second.length ≤ 1051 ≤ first.length + second.length-231 ≤ first[i], second[j] ≤ 231 − 1firstandsecondare each sorted in non-decreasing order.
Clarifying questions
What you would ask an interviewer before writing any code.