Median of Two Sorted Arrays

Problem Statement

You are given two sorted arrays nums1 and nums2 of sizes m and n.
Find the median of the two sorted arrays.

The overall time complexity should be O(log (m + n)).

Example 1

Input

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

Output

2.0

Example 2

Input

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

Output

2.5

Why This Problem Is Important

• Very famous hard-level interview problem
• Tests deep understanding of binary search on arrays
• Requires strong logical partitioning
• Asked frequently by top tech companies
• Foundation for advanced divide-and-conquer techniques

Key Observations

• Median depends on total length (even or odd)
• We do not need to merge the arrays
• Binary search can be applied on the smaller array
• Correct partition gives median in logarithmic time

Approaches Overview

Approach 1: Merge Both Arrays

Idea

Merge the two arrays into one sorted array and find the median.

Drawback

Does not meet the required time complexity.

Time & Space Complexity

• Time: O(m + n)
• Space: O(m + n)

C Implementation 

#include 

int main() {
    int nums1[] = {1, 2};
    int nums2[] = {3, 4};
    int m = sizeof(nums1) / sizeof(nums1[0]);
    int n = sizeof(nums2) / sizeof(nums2[0]);

    int merged[m + n];
    int i = 0, j = 0, k = 0;

    while (i < m && j < n) {
        if (nums1[i] < nums2[j])
            merged[k++] = nums1[i++];
        else
            merged[k++] = nums2[j++];
    }

    while (i < m)
        merged[k++] = nums1[i++];

    while (j < n)
        merged[k++] = nums2[j++];

    double median;
    int total = m + n;
    if (total % 2 == 0)
        median = (merged[total/2 - 1] + merged[total/2]) / 2.0;
    else
        median = merged[total/2];

    printf("Median = %.1f\n", median);
    return 0;
}

Output

Median = 2.5

C++ Implementation 

#include 
#include 
using namespace std;

int main() {
    vector nums1 = {1, 2};
    vector nums2 = {3, 4};

    vector merged;
    int i = 0, j = 0;

    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j])
            merged.push_back(nums1[i++]);
        else
            merged.push_back(nums2[j++]);
    }

    while (i < nums1.size()) merged.push_back(nums1[i++]);
    while (j < nums2.size()) merged.push_back(nums2[j++]);

    int total = merged.size();
    double median;
    if (total % 2 == 0)
        median = (merged[total/2 - 1] + merged[total/2]) / 2.0;
    else
        median = merged[total/2];

    cout << "Median = " << median << endl;
    return 0;
}

Output

Median = 2.5

Java Implementation 

public class MedianMergeApproach {
    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};

        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) {
            if (nums1[i] < nums2[j])
                merged[k++] = nums1[i++];
            else
                merged[k++] = nums2[j++];
        }

        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];

        double median;
        int total = m + n;

        if (total % 2 == 0)
            median = (merged[total/2 - 1] + merged[total/2]) / 2.0;
        else
            median = merged[total/2];

        System.out.println("Median = " + median);
    }
}

Output

Median = 2.5

Python Implementation 

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

merged = sorted(nums1 + nums2)
total = len(merged)

if total % 2 == 0:
    median = (merged[total//2 - 1] + merged[total//2]) / 2
else:
    median = merged[total//2]

print("Median =", median)

Output

Median = 2.5

JavaScript Implementation 

let nums1 = [1, 2];
let nums2 = [3, 4];

let merged = nums1.concat(nums2).sort((a, b) => a - b);
let total = merged.length;

let median;
if (total % 2 === 0)
    median = (merged[total/2 - 1] + merged[total/2]) / 2;
else
    median = merged[Math.floor(total/2)];

console.log("Median =", median);

Output

Median = 2.5

Next: Approach 2 — Two Pointers (O(m+n), O(1) space).

Approach 2: Two Pointers

Idea

Simulate the merge process and stop once the median position is reached.

Time & Space Complexity

• Time: O(m + n)
• Space: O(1)

C++ Implementation 

#include 
#include 
using namespace std;

double findMedianSortedArrays(vector& nums1, vector& nums2) {
    int m = nums1.size(), n = nums2.size();
    int total = m + n;
    int i = 0, j = 0;

    int prev = 0, curr = 0;

    for (int count = 0; count <= total / 2; count++) {
        prev = curr;

        if (i < m && (j >= n || nums1[i] < nums2[j]))
            curr = nums1[i++];
        else
            curr = nums2[j++];
    }

    if (total % 2 == 0)
        return (prev + curr) / 2.0;
    else
        return curr;
}

int main() {
    vector nums1 = {1, 2};
    vector nums2 = {3, 4};

    cout << findMedianSortedArrays(nums1, nums2);
    return 0;
}

Output

2.5

Java Implementation 

public class MedianTwoPointers {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int i = 0, j = 0;

        int prev = 0, curr = 0;

        for (int count = 0; count <= total / 2; count++) {
            prev = curr;

            if (i < m && (j >= n || nums1[i] < nums2[j]))
                curr = nums1[i++];
            else
                curr = nums2[j++];
        }

        if (total % 2 == 0)
            return (prev + curr) / 2.0;
        else
            return curr;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};

        System.out.println(findMedianSortedArrays(nums1, nums2));
    }
}

Output

2.5

Python Implementation 

def findMedianSortedArrays(nums1, nums2):
    m, n = len(nums1), len(nums2)
    total = m + n
    i = j = 0
    prev = curr = 0

    for _ in range(total // 2 + 1):
        prev = curr

        if i < m and (j >= n or nums1[i] < nums2[j]):
            curr = nums1[i]
            i += 1
        else:
            curr = nums2[j]
            j += 1

    if total % 2 == 0:
        return (prev + curr) / 2
    else:
        return curr


# Driver Code
nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays(nums1, nums2))

Output

2.5

JavaScript Implementation

function findMedianSortedArrays(nums1, nums2) {
    let m = nums1.length, n = nums2.length;
    let total = m + n;
    let i = 0, j = 0;
    let prev = 0, curr = 0;

    for (let count = 0; count <= Math.floor(total / 2); count++) {
        prev = curr;

        if (i < m && (j >= n || nums1[i] < nums2[j]))
            curr = nums1[i++];
        else
            curr = nums2[j++];
    }

    if (total % 2 === 0)
        return (prev + curr) / 2;
    else
        return curr;
}

// Driver
console.log(findMedianSortedArrays([1,2], [3,4]));

Output

2.5

Approach 3: Binary Search Partition (Optimal)

Core Idea

Partition both arrays such that:

• Left half contains exactly half of the elements
• All elements in left half ≤ all elements in right half

Algorithm

1. Ensure nums1 is the smaller array

2. Initialize:

   low = 0
   high = len(nums1)
   

3. While low <= high:

   • Compute partition positions:

     cut1 = (low + high) / 2
     cut2 = (m + n + 1) / 2 - cut1
     

   • Define boundaries:

     left1, right1
     left2, right2
     

   • If valid partition:
     • If total length is even → median is average of max(left) and min(right)
     • Else → median is max(left)
   • Else adjust binary search

Time & Space Complexity

• Time: O(log(min(m, n)))
• Space: O(1)

C Implementation 

#include 
#include 

double findMedianSortedArrays(int a[], int m, int b[], int n) {
    if (m > n)
        return findMedianSortedArrays(b, n, a, m);

    int low = 0, high = m;

    while (low <= high) {
        int cut1 = (low + high) / 2;
        int cut2 = (m + n + 1) / 2 - cut1;

        int left1  = (cut1 == 0) ? INT_MIN : a[cut1 - 1];
        int right1 = (cut1 == m) ? INT_MAX : a[cut1];

        int left2  = (cut2 == 0) ? INT_MIN : b[cut2 - 1];
        int right2 = (cut2 == n) ? INT_MAX : b[cut2];

        if (left1 <= right2 && left2 <= right1) {
            if ((m + n) % 2 == 0)
                return ( (left1 > left2 ? left1 : left2) +
                         (right1 < right2 ? right1 : right2) ) / 2.0;
            else
                return (left1 > left2 ? left1 : left2);
        }
        else if (left1 > right2)
            high = cut1 - 1;
        else
            low = cut1 + 1;
    }
    return 0.0;
}

int main() {
    int nums1[] = {1, 2};
    int nums2[] = {3, 4};
    int m = 2, n = 2;

    double median = findMedianSortedArrays(nums1, m, nums2, n);
    printf("%.1f", median);
    return 0;
}

Output

2.5

C++ Implementation 

#include 
#include 
#include 
using namespace std;

double findMedianSortedArrays(vector& a, vector& b) {
    if (a.size() > b.size())
        return findMedianSortedArrays(b, a);

    int m = a.size(), n = b.size();
    int low = 0, high = m;

    while (low <= high) {
        int cut1 = (low + high) / 2;
        int cut2 = (m + n + 1) / 2 - cut1;

        int left1  = (cut1 == 0) ? INT_MIN : a[cut1 - 1];
        int right1 = (cut1 == m) ? INT_MAX : a[cut1];

        int left2  = (cut2 == 0) ? INT_MIN : b[cut2 - 1];
        int right2 = (cut2 == n) ? INT_MAX : b[cut2];

        if (left1 <= right2 && left2 <= right1) {
            if ((m + n) % 2 == 0)
                return (max(left1, left2) + min(right1, right2)) / 2.0;
            else
                return max(left1, left2);
        }
        else if (left1 > right2)
            high = cut1 - 1;
        else
            low = cut1 + 1;
    }
    return 0.0;
}

int main() {
    vector nums1 = {1, 2};
    vector nums2 = {3, 4};

    cout << findMedianSortedArrays(nums1, nums2);
    return 0;
}

Output

2.5

Java Implementation 

public class MedianBinarySearch {

    public static 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 cut1 = (low + high) / 2;
            int cut2 = (m + n + 1) / 2 - cut1;

            int left1  = (cut1 == 0) ? Integer.MIN_VALUE : a[cut1 - 1];
            int right1 = (cut1 == m) ? Integer.MAX_VALUE : a[cut1];

            int left2  = (cut2 == 0) ? Integer.MIN_VALUE : b[cut2 - 1];
            int right2 = (cut2 == n) ? Integer.MAX_VALUE : b[cut2];

            if (left1 <= right2 && left2 <= right1) {
                if ((m + n) % 2 == 0)
                    return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
                else
                    return Math.max(left1, left2);
            }
            else if (left1 > right2)
                high = cut1 - 1;
            else
                low = cut1 + 1;
        }
        return 0.0;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};

        System.out.println(findMedianSortedArrays(nums1, nums2));
    }
}

Output

2.5

Python Implementation 

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        return findMedianSortedArrays(nums2, nums1)

    m, n = len(nums1), len(nums2)
    low, high = 0, m

    while low <= high:
        cut1 = (low + high) // 2
        cut2 = (m + n + 1) // 2 - cut1

        left1 = float('-inf') if cut1 == 0 else nums1[cut1 - 1]
        right1 = float('inf') if cut1 == m else nums1[cut1]

        left2 = float('-inf') if cut2 == 0 else nums2[cut2 - 1]
        right2 = float('inf') if cut2 == n else nums2[cut2]

        if left1 <= right2 and left2 <= right1:
            if (m + n) % 2 == 0:
                return (max(left1, left2) + min(right1, right2)) / 2
            else:
                return max(left1, left2)
        elif left1 > right2:
            high = cut1 - 1
        else:
            low = cut1 + 1

    return 0.0


# Driver Code
nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays(nums1, nums2))

Output

2.5

JavaScript Implementation 

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length)
        return findMedianSortedArrays(nums2, nums1);

    let m = nums1.length, n = nums2.length;
    let low = 0, high = m;

    while (low <= high) {
        let cut1 = Math.floor((low + high) / 2);
        let cut2 = Math.floor((m + n + 1) / 2) - cut1;

        let left1 = (cut1 === 0) ? -Infinity : nums1[cut1 - 1];
        let right1 = (cut1 === m) ? Infinity : nums1[cut1];

        let left2 = (cut2 === 0) ? -Infinity : nums2[cut2 - 1];
        let right2 = (cut2 === n) ? Infinity : nums2[cut2];

        if (left1 <= right2 && left2 <= right1) {
            if ((m + n) % 2 === 0)
                return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
            else
                return Math.max(left1, left2);
        }
        else if (left1 > right2)
            high = cut1 - 1;
        else
            low = cut1 + 1;
    }
    return 0;
}

// Driver
console.log(findMedianSortedArrays([1,2], [3,4]));

Output

2.5

Summary

• Do not merge arrays
• Binary search on smaller array
• Partition logic ensures correctness
• Optimal and interview-preferred solution

Next Problem in the Series

Merge Intervals