# Median of Two Sorted Arrays

2 min read Tweet this post
Section titled Problem

## 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.00000
Explanation: merged array = [1,2,2] and median is 2.``````

Example 2:

``````Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.``````
Section titled Solution

## Solution

Section titled %24O%28n+m%29%24%20Brute%20Force

### \$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`
``````
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
}``````
``````// using internal sorting golang
import "sort"

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
nums1 = append(nums1, nums2...)
sort.Ints(nums1)
midIndex := len(nums1) / 2
if len(nums1)%2 == 1 {
return float64(nums1[midIndex])
}

return float64(nums1[midIndex-1]+nums1[midIndex]) / 2.0
}``````
Section titled %24O%28log%28n+m%29%29%24%20solution

### \$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`
``````
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
}
``````
Section titled Reference

## Reference

go data-structure array