Course4all
Join us on telegram
Home/dsa/Binary Search/Median of Two Sorted Arrays

Median of Two Sorted Arrays

Master this topic with zero to advance depth.

Median of Two Sorted Arrays

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))O(\\log (m+n)).

Hard

Examples

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Approach 1

Level I: Merge and Find

Intuition

Use the merge step of merge sort to combine the two arrays into one sorted array. Then find the middle element(s).

⏱ $O(M + N)$💾 $O(M + N)$

Detailed Dry Run

nums1 = [1,3], nums2 = [2] Merged: [1,2,3]. n=3. Median: Index 1 (Value 2).

java
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) merged[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];
        int total = m + n;
        if (total % 2 == 1) return merged[total / 2];
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
    }
}
Approach 2

Level II: Recursive K-th Element

Intuition

Find the kk-th smallest element in two sorted arrays by comparing the middle elements of each array (divided by 2 at each step).

⏱ $O(\log(M+N))$💾 $O(\log(M+N))$ due to recursion stack.

Detailed Dry Run

Find 5th element in [1,3,5,...] and [2,4,6,...]. Compare 2nd elements...

java
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        if (n % 2 == 1) return getKth(nums1, 0, nums2, 0, n / 2 + 1);
        return (getKth(nums1, 0, nums2, 0, n / 2) + getKth(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
    }
    private int getKth(int[] a, int aS, int[] b, int bS, int k) {
        if (aS >= a.length) return b[bS + k - 1];
        if (bS >= b.length) return a[aS + k - 1];
        if (k == 1) return Math.min(a[aS], b[bS]);
        int aMid = aS + k/2 - 1 < a.length ? a[aS + k/2 - 1] : Integer.MAX_VALUE;
        int bMid = bS + k/2 - 1 < b.length ? b[bS + k/2 - 1] : Integer.MAX_VALUE;
        if (aMid < bMid) return getKth(a, aS + k/2, b, bS, k - k/2);
        return getKth(a, aS, b, bS + k/2, k - k/2);
    }
}
Approach 3

Level III: Optimal (Binary Search on Partitions)

Intuition

We can binary search for the correct partition point in the smaller array. A partition is correct if all elements on the left side are smaller than all elements on the right side.

⏱ $O(\\log(\\min(M, N)))$💾 $O(1)$

Detailed Dry Run

nums1 = [1,3], nums2 = [2]

  1. BS on nums1. Low=0, High=2. i=1. j = (2+1+1)/2 - 1 = 1.
  2. LeftA=1, RightA=3, LeftB=2, RightB=inf.
  3. LeftA <= RightB (1 <= inf) and LeftB <= RightA (2 <= 3). Correct!
  4. Median: max(1, 2) = 2.0.
java
class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        if (A.length > B.length) return findMedianSortedArrays(B, A);
        int m = A.length, n = B.length;
        int low = 0, high = m;
        while (low <= high) {
            int i = low + (high - low) / 2;
            int j = (m + n + 1) / 2 - i;
            int LA = (i == 0) ? Integer.MIN_VALUE : A[i - 1];
            int RA = (i == m) ? Integer.MAX_VALUE : A[i];
            int LB = (j == 0) ? Integer.MIN_VALUE : B[j - 1];
            int RB = (j == n) ? Integer.MAX_VALUE : B[j];
            if (LA <= RB && LB <= RA) {
                if ((m + n) % 2 == 0) return (Math.max(LA, LB) + Math.min(RA, RB)) / 2.0;
                return Math.max(LA, LB);
            } else if (LA > RB) high = i - 1;
            else low = i + 1;
        }
        return 0.0;
    }
}
← Previous QuestionSplit Array Largest Sum
Next Question →Find K-th Smallest Pair Distance