Find Median of Two Sorted Arrays (Different Sizes) - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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❯

Understanding the Problem

We are given two sorted arrays, possibly of different sizes. Our goal is to find the median of the combined data. However, we are not allowed to merge the two arrays because that would take extra time and space.

The challenge is to find the median efficiently—ideally in O(log(min(n, m)) time—by leveraging the fact that the arrays are already sorted.

The median is the middle value in a sorted list. If the combined number of elements is odd, it's the exact middle element. If even, it's the average of the two middle elements.

Step-by-Step Solution with Example

Step 1: Choose the Shorter Array for Binary Search

We always perform binary search on the smaller of the two arrays to minimize the time complexity. Let's call the two arrays nums1 and nums2.

Example: Let nums1 = [1, 3] and nums2 = [2, 4, 5]

Step 2: Calculate Total Length and Half Length

Total number of elements = 5, which is odd.

Half length (for partitioning) = (5 + 1) / 2 = 3.

Step 3: Apply Binary Search on nums1

We’ll apply binary search to find a partition index i in nums1, and calculate j = half - i for nums2.

Step 4: Define Left and Right Elements at Partition

We compare the elements around the partition to ensure the following:

  • nums1[i - 1] ≤ nums2[j]
  • nums2[j - 1] ≤ nums1[i]

If this is true, we’ve found the correct partition.

Step 5: Calculate the Median Based on Partition

In our example, one possible partition is:

  • nums1 = [1, 3] → i = 2
  • nums2 = [2, 4, 5] → j = 1

Left half = [1, 2, 3], Right half = [4, 5]

The median is the maximum of the left half = 3, because total number is odd.

Step 6: Adjust Binary Search if Partition Is Incorrect

If the partition condition is not met (e.g., nums1[i - 1] > nums2[j]), we move left. If nums2[j - 1] > nums1[i], we move right. This continues until we find the correct split.

Edge Cases

  • One array is empty: If nums1 is empty and nums2 = [1, 2, 3], the median is just 2.
  • Both arrays are empty: No median can be defined. Return an error or a null result.
  • Arrays have duplicate values or zeros: The binary search-based logic still works since it relies on comparisons, not uniqueness.
  • Arrays are of very different lengths: The algorithm remains efficient as it only searches the smaller array.

Finally

This solution avoids merging the arrays and achieves logarithmic time complexity using binary search. It carefully balances the elements on both sides of a conceptual partition to directly identify the median.

It’s efficient, elegant, and perfect for large datasets where a full merge would be too slow.

Algorithm Steps❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <limits.h>
#include <math.h>

double findMedianSortedArrays(int* nums1, int n1, int* nums2, int n2) {
    if (n1 > n2) return findMedianSortedArrays(nums2, n2, nums1, n1);

    int low = 0, high = n1;
    while (low <= high) {
        int px = (low + high) / 2;
        int py = (n1 + n2 + 1) / 2 - px;

        int maxLeftX = (px == 0) ? INT_MIN : nums1[px - 1];
        int minRightX = (px == n1) ? INT_MAX : nums1[px];

        int maxLeftY = (py == 0) ? INT_MIN : nums2[py - 1];
        int minRightY = (py == n2) ? INT_MAX : nums2[py];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((n1 + n2) % 2 == 0)
                return (fmax(maxLeftX, maxLeftY) + fmin(minRightX, minRightY)) / 2.0;
            else
                return fmax(maxLeftX, maxLeftY);
        } else if (maxLeftX > minRightY) {
            high = px - 1;
        } else {
            low = px + 1;
        }
    }
    return 0.0;
}

int main() {
    int nums1[] = {1, 3};
    int nums2[] = {2};
    int n1 = 2, n2 = 1;
    double result = findMedianSortedArrays(nums1, n1, nums2, n2);
    printf("Median is: %lf\n", result);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)Median found on the first partition guess if the arrays are perfectly balanced.
Average CaseO(log(min(n, m)))Binary search on the smaller array ensures logarithmic steps for finding the correct partition.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...