Median of Two Sorted Arrays
- 4 min read
- LC-Hard
- Binary-search
3 years ago
Solution
- Our goal is to find the left sorted portion of the array. Across two arrays, this means we basically find at which point in both arrays to stop so that the number of elements combined across both left partitions of the array is roughly equal to the sum of the number of elements in both the right parts of both arrays
- Now obviously, the cases will be a bit different across odd-numbered and even numbered arrays, but this only affects our calculation of the median.
- Also keep in mind that we will only be doing a binary search on the smaller array.
- First, we precalculate the sizes and the half size. Take this example:
- B: [1, 2, 3, 4, 5, 6, 7, 8]
- A: [1, 2, 3, 4, 5]
- Our
totalsize is equal to length of both arrays combined, so it's 13. Ourhalfis equal tototal // 2which is 6.
- When doing binary search on the smaller array A, we end up with 3 as the mid element. Our size of the left partition (from
lup tomid) is 3. - This means that our requisite size of the partition on the larger array B is
half - 3which equals 3 - So currently, our left partitions in both arrays are
- B: [1, 2, 3]
- A: [1, 2, 3]
- To check if we've met a valid condition to begin calculating the median, we need to check if the last element in the left partition of each array is lesser than or equal to the element that comes after the last element in the other array.
- This only happens if we've partitioned our array properly- the arrays themselves are individually sorted, and conceptually they are one array, so we need to check for this condition.
- To help out with boundary conditions when we're checking our partition property, we have additional checks if our index is out of bounds. If they are, the value we will compare with is negative and positive infinity (look at the code to understand)
- This cleans up our code a lot
- The values inside the min() function calls will never have infinities for both values. Do a dry run to confirm this.
- To help out with boundary conditions when we're checking our partition property, we have additional checks if our index is out of bounds. If they are, the value we will compare with is negative and positive infinity (look at the code to understand)
- If this condition is not met, we either need to reduce or increase the partition of our smaller array- this is where the actual binary search is being done
- Once our partition condition is met, we can calculate the median and return.
- If the number of elements is odd, just take the minimum of the last elements in both left partitions of both arrays and return
- If the number of elements is even, take the maximum of last elements in both left partitions of both arrays, and the minimum of first elements in the right partitions of both arrays, and add these up, divide by 2. This is your median
- First, we precalculate the sizes and the half size. Take this example:
| Time | Space | Explanation |
|---|---|---|
O(log(min(m, n))) | O() |
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A, B = nums1, nums2
if len(A) > len(B):
A, B = B, A
total = len(A) + len(B)
half = total // 2
l, r = 0, len(A) - 1
while True:
a = (l + r) // 2
b = half - a - 2
a_left = A[a] if a >= 0 else -math.inf
b_left = B[b] if b >= 0 else -math.inf
a_right = A[a + 1] if a + 1 < len(A) else math.inf
b_right = B[b + 1] if b + 1 < len(B) else math.inf
if a_left <= b_right and b_left <= a_right:
if total % 2 == 0:
return (max(a_left, b_left) + min(a_right, b_right)) / 2
else:
return min(a_right, b_right)
elif a_left > b_right:
r = a - 1
else:
l = a + 1