Find Median of Two Sorted Arrays (Different Sizes)
Optimal Binary Search Approach

⬅ Previous Topic

Minimize Maximum Distance Between Gas Stations

Next Topic ⮕

Topic Contents

Problem Examples Solution Visualization Algorithm Code Time Space

Problem Statement

You are given two sorted arrays that can be of different sizes. Your task is to find the median of the combined sorted array formed by merging the two arrays.

The median is the middle value in the combined array if its length is odd.
If the total length is even, the median is the average of the two middle numbers.

Try to solve the problem in an efficient way using binary search, with a time complexity of O(log(min(n, m)), where n and m are the lengths of the two arrays.

Examples❯

Array 1	Array 2	Median	Description
[1, 3, 8]	[7, 9, 10, 11]	8.0	Merged array is [1, 3, 7, 8, 9, 10, 11] → median is 8 (middle element)
[1, 2]	[3, 4]	2.5	Merged: [1, 2, 3, 4] → even length → (2 + 3) / 2 = 2.5
[0, 0]	[0, 0]	0.0	All elements are 0 → median is 0
[]	[1]	1.0	Only one array has data → median is that element
[2]	[]	2.0	Only one array has data → median is that element
[]	[]	undefined	Both arrays are empty → no median exists
[1, 3]	[2]	2.0	Merged: [1, 2, 3] → odd length → median is 2
[1, 2, 3, 4, 5]	[6, 7, 8, 9, 10, 11]	6.0	Merged length = 11 → middle element is 6

Solution❯

To find the median of two sorted arrays of different sizes, we need to locate the middle value(s) of their combined sorted order—but without actually merging the arrays. Instead, we use a smart technique based on binary search to find the right partitioning between the two arrays.

What is a Median?

The median is the value that separates the lower half and upper half of a dataset. For an odd total number of elements, it's the exact middle. For an even number of elements, it's the average of the two middle values.

Key Idea

We want to split both arrays into two halves—left_half and right_half—such that:

The number of elements in the left half = number of elements in the right half (or one more if the total is odd)
The maximum of the left half ≤ the minimum of the right half

Once this condition is met, the median will either be:

max(left_half) if total length is odd
(max(left_half) + min(right_half)) / 2 if total length is even

How It Works

We apply binary search on the shorter array (for efficiency). At each step, we pick a partition index in the first array and calculate the corresponding partition in the second array to keep the total elements in left and right balanced.

We then check whether the largest element in the left part of array 1 and 2 is less than or equal to the smallest in the right part of array 1 and 2. If yes, we’ve found the correct partition.

If not, we adjust our binary search boundaries—moving left or right—until the correct split is found.

Edge Cases to Consider

If one array is empty, the median is simply the median of the other array.
If both arrays are empty, there is no median; it should return undefined or a suitable error.
If arrays contain duplicate values or zeros, the logic still holds since all comparisons are value-based.

Why This Approach?

Instead of merging arrays (which takes O(n + m) time), we use binary search on the smaller array, reducing time complexity to O(log(min(n, m))). This is optimal and works well even with large arrays.

This approach is powerful, elegant, and leverages the sorted nature of both arrays to avoid extra work.

Visualization

Algorithm Steps

Let the two arrays be nums1 and nums2. Always apply binary search on the smaller array to minimize time.
Set low = 0 and high = length of nums1.
While low ≤ high, do the following:
→ Compute partitionX = (low + high) / 2.
→ Compute partitionY = (n + m + 1)/2 - partitionX.
→ Find maxLeftX, minRightX, maxLeftY, and minRightY using partition indices.
→ If maxLeftX ≤ minRightY and maxLeftY ≤ minRightX, you found the correct partition.
→ Compute median depending on even/odd total length.
If not, adjust low or high accordingly.
If no partition is found, return 0 (edge case safety).

Code

Python

Java

C++

JavaScript

Kotlin

Swift

Php

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

    x, y = len(nums1), len(nums2)
    low, high = 0, x

    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (x + y + 1) // 2 - partitionX

        maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
        minRightX = float('inf') if partitionX == x else nums1[partitionX]

        maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
        minRightY = float('inf') if partitionY == y else nums2[partitionY]

        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (x + y) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0
            else:
                return max(maxLeftX, maxLeftY)
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1

    return 0.0

print(findMedianSortedArrays([1, 3], [2]))

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(1)	Median found on the first partition guess if the arrays are perfectly balanced.
Average Case	O(log(min(n, m)))	Binary search on the smaller array ensures logarithmic steps for finding the correct partition.
Worst Case	O(log(min(n, m)))	In worst case, binary search continues until all elements in the smaller array are checked.

Space Complexity

O(1)

Explanation: Only a fixed number of variables are used for partitioning logic. No extra space is required.

⬅ Previous Topic

Minimize Maximum Distance Between Gas Stations

Next Topic ⮕

K-th Element of Two Sorted Arrays

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Find Median of Two Sorted Arrays (Different Sizes)
Optimal Binary Search Approach

Problem Statement

Examples❯

Solution❯

What is a Median?

Key Idea

How It Works

Edge Cases to Consider

Why This Approach?

Visualization

Algorithm Steps

Code

Time Complexity

Space Complexity

Support ProgramGuru.org❯

Find Median of Two Sorted Arrays (Different Sizes)Optimal Binary Search Approach

Problem Statement

Examples❯

Solution❯

What is a Median?

Key Idea

How It Works

Edge Cases to Consider

Why This Approach?

Visualization

Algorithm Steps

Code

Time Complexity

Space Complexity

Welcome to ProgramGuru

Support ProgramGuru.org❯

Find Median of Two Sorted Arrays (Different Sizes)
Optimal Binary Search Approach