Median of Two Sorted Arrays

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.

Solution

$O(n+m)$ Brute Force

This solution start with merding 2 sorted array
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
}

$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
}

Reference

https://leetcode.com/problems/median-of-two-sorted-arrays/solutions/2471/very-concise-o-log-min-m-n-iterative-solution-with-detailed-explanation/