4. Median of Two Sorted Arrays

Problem Link

We can find the median of a single sorted array in \(O(1)\) time by directly computing the middle indexes. However, this problem requires finding the median of two sorted arrays without merging them, while achieving a time complexity better than \(O(m+n)\).

Instead of merging, we apply binary search on the smaller array to find a valid partition between the two arrays such that:

• The total number of elements on the left side equals the total number on the right side (or differs by one).
• All elements on the left partition are less than or equal to all elements on the right partition.

Let the partition index in the first array be \(i\), and in the second array be \(j\), where \(i+j= {m+n+1 \over 2}\). This ensures the left partition contains the correct number of elements. Using binary search, we adjust \(i\) until \(nums1[i - 1] \le nums2[j]\) and \(nums2[j - 1] \le nums1[i]\). Once a valid partition is found:

• If the total length is odd, the median is the maximum element on the left side.
• If the total length is even, the median is the average of the maximum of the left side and the minimum of the right side.

To optimize the binary search runtime, you can perform it on smaller array.

Runtime Complexity

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

Space: \(O(1)\)

PythonGo

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        A, B = nums1, nums2
        if len(A) > len(B):
            A, B = B, A

        half = (len(A)+len(B))//2
        left, right = 0, len(A)-1
        while True:
            midA = left + (right-left)//2
            midB = half - midA - 2
            Aleft = A[midA] if midA >= 0 else float('-inf')
            Aright = A[midA+1] if midA+1 < len(A) else float('inf')
            Bleft = B[midB] if midB >= 0 else float('-inf')
            Bright = B[midB+1] if midB+1 < len(B) else float('inf')
            if Aleft <= Bright and Bleft <= Aright:
                if (len(A)+len(B))%2 == 0:
                    return (max(Aleft,Bleft) + min(Aright, Bright))/2
                else:
                    return min(Aright, Bright)
            elif Aleft > Bright:
                right = midA-1
            else:
                left = midA+1

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

    m, n := len(nums1), len(nums2)
    half := (m + n + 1) / 2

    low, high := 0, m

    for low <= high {
        partA := (low + high) / 2
        partB := half - partA

        var leftA, rightA int
        if partA == 0 {
            leftA = math.MinInt64
        } else {
            leftA = nums1[partA-1]
        }
        if partA == m {
            rightA = math.MaxInt64
        } else {
            rightA = nums1[partA]
        }

        var leftB, rightB int
        if partB == 0 {
            leftB = math.MinInt64
        } else {
            leftB = nums2[partB-1]
        }
        if partB == n {
            rightB = math.MaxInt64
        } else {
            rightB = nums2[partB]
        }

        if leftA <= rightB && leftB <= rightA {
            if (m+n)%2 == 0 {
                return (float64(max(leftA, leftB)) + float64(min(rightA, rightB))) / 2
            }
            return float64(max(leftA, leftB))
        } else if leftA > rightB {
            high = partA - 1
        } else {
            low = partA + 1
        }
    }
    return 0
}

---