Problem Description

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)).

Problem Link

Solution 1: Merge Array

Merge two arrays into one array, and then find the median. But this solution doesn’t meet the requirement of O(log( m+n)).

Code

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    res := make([]int, 0, len(nums1)+len(nums2))
    i, j := 0, 0
    for i < len(nums1) && j < len(nums2) {
       if nums1[i] <= nums2[j] {
          res = append(res, nums1[i])
          i++
       } else {
          res = append(res, nums2[j])
          j++
       }
    }

    for i < len(nums1) {
       res = append(res, nums1[i])
       i++
    }

    for j < len(nums2) {
       res = append(res, nums2[j])
       j++
    }

    n := len(res)
    if n%2 == 0 {
       mid := n / 2
       return float64(res[mid]+res[mid-1]) / 2.0
    } else {
       return float64(res[n/2])
    }

Time Complexity: O(m+n)

Space Complexity: O(m+n)

Solution 2 : Binary Search

Instead of actually merging the arrays, we use binary search to find the perfect partition point that divides both arrays into left and right halves, where:

• Left half has exactly (m + n + 1) / 2 elements
• Every element in left half ≤ every element in right half

Key Insight

Since both arrays are already sorted internally, we only need to check the cross-boundary conditions:

maxLeftX ≤ minRightY  &&  maxLeftY ≤ minRightX

Algorithm Flow

1. Binary search on the shorter array (to ensure efficiency)
2. Calculate partition points:
   • partitionX = (left + right) / 2
   • partitionY = (m + n + 1) / 2 - partitionX
3. Extract boundary values from both partitions
4. Check the partition condition:
   • If valid → calculate median
   • If maxLeftX > minRightY → move left (too many from nums1)
   • If maxLeftY > minRightX → move right (too few from nums1)

Code

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
       return findMedianSortedArrays(nums2, nums1)
    }

    m, n := len(nums1), len(nums2)
    left, right := 0, m

    for left <= right {
       partitionX := (left + right) / 2
       partitionY := (m+n+1)/2 - partitionX

       maxLeftX := math.MinInt32
       if partitionX > 0 {
          maxLeftX = nums1[partitionX-1]
       }

       minRightX := math.MaxInt32
       if partitionX < m {
          minRightX = nums1[partitionX]
       }

       maxLeftY := math.MinInt32
       if partitionY > 0 {
          maxLeftY = nums2[partitionY-1]
       }

       minRightY := math.MaxInt32
       if partitionY < n {
          minRightY = nums2[partitionY]
       }

       if maxLeftX <= minRightY && maxLeftY <= minRightX {
          if (m+n)%2 == 0 {
             return float64(max(maxLeftX, maxLeftY)+min(minRightX, minRightY)) / 2.0
          } else {
             return float64(max(maxLeftX, maxLeftY))
          }
       } else if maxLeftX > minRightY {
          right = partitionX - 1
       } else {
          left = partitionX + 1
       }
    }
    return 0
}

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
}

Time Complexity: O(log(min(m,n)))

We only binary search on the shorter array, and each iteration cuts the search space in half.

Space Complexity: O(1)

Only uses constant extra space for boundary variables. This approach transforms a linear merging problem into a logarithmic search problem by cleverly exploiting the sorted nature of the input arrays