Median of Two Sorted Arrays

# Median of Two Sorted Arrays

January 30, 2023

Name
Moch Lutfi
@kaptenupi

## 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

### $O(n+m)$ Brute Force

• Find mid index from merged arrays len(mergedArray)/2 as midIndex
• If length is odd, return value from mergedArray[midIndex]
• Otherwise, return value from (mergedArray[midIndex] + mergedArray[midIndex-1]) / 2
onm.go
onmsort.go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { m, n := len(nums1), len(nums2) nums1 = append(nums1, make([]int, len(nums2))...) for n > 0 { if m == 0 || nums2[n-1] > nums1[m-1] { nums1[m+n-1] = nums2[n-1] n-- } else { nums1[m+n-1] = nums1[m-1] m-- } } midIndex := len(nums1) / 2 if len(nums1)%2 == 1 { return float64(nums1[midIndex]) } return float64(nums1[midIndex-1]+nums1[midIndex]) / 2.0}

### $O(log(n+m))$ 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 . . . ] and nums2 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 of nums1.
• If L2 > R1, we know current cutting position is incorrect. A valid cutting position for median should be on the right half of nums1.
• If L1 < R2 and L2 < R1, that's the result. median = (max(L1, L2) + min(R1, R2)) / 2
olognm.go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { n1 := len(nums1) n2 := len(nums2) if n1 < n2 { return findMedianSortedArrays(nums2, nums1) } lo, hi := 0, n2*2 for lo <= hi { mid2 := (lo + hi) / 2 mid1 := n1 + n2 - mid2 l1 := math.MinInt64 if mid1 != 0 { l1 = nums1[(mid1-1)/2] } l2 := math.MinInt64 if mid2 != 0 { l2 = nums2[(mid2-1)/2] } r1 := math.MaxInt64 if mid1 != n1*2 { r1 = nums1[mid1/2] } r2 := math.MaxInt64 if mid2 != n2*2 { r2 = nums2[mid2/2] } if l1 > r2 { lo = mid2 + 1 } else if l2 > r1 { hi = mid2 - 1 } else { return float64(max(l1, l2)+min(r1, r2)) / 2.0 } } return -1}func max(a, b int) int { if a > b { return a } return b}func min(a, b int) int { if a < b { return a } return b}