Median of Two Sorted Arrays
January 30, 2023
Problem
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)).
Example 1:Input: nums1 = [1,2], nums2 = [2]Output: 2.00000Explanation: merged array = [1,2,2] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]Output: 2.50000Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Solution
Brute Force
- This solution start with merding 2 sorted array
- Find mid index from merged arrays
len(mergedArray)/2
asmidIndex
- If length is odd, return value from
mergedArray[midIndex]
- Otherwise, return value from
(mergedArray[midIndex] + mergedArray[midIndex-1]) / 2
- If length is odd, return value from
solution
- Median is defined as the average of the two middle elements in a sorted array.
- The median can be represented as (A[(N-1)/2] + A[N/2])/2 in a one-array situation.
- The cut positions in a two-array situation can be determined by the number of positions in each array and the desired cut position in one of the arrays.
nums1
into[. . . . L1 | R1 . . . ]
andnums2
into[. . . . L2 | R2 . . . ]
respectively. so that[. . . . L1] + [. . . . L2]
has equal number of elements as[R1 . . . ] + [R2 . . . ]
. The goal is to find such cutting positions that give us the median values. - The left and right elements at each cut position are found by using the formula
L = A[(C-1)/2]
R = A[C/2]
- Using binary search, If
L1 > R2
, we know current cutting position is incorrect. A valid cutting position for median should be on the left half ofnums1
. - If
L2 > R1
, we know current cutting position is incorrect. A valid cutting position for median should be on the right half ofnums1
. - If
L1 < R2
andL2 < R1
, that's the result.median = (max(L1, L2) + min(R1, R2)) / 2