Course4all

Median of Two Sorted Arrays

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

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

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSplit Array Largest Sum
Next Question →Find K-th Smallest Pair Distance