Median of Two Sorted Arrays of Different Sizes

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.

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.

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).

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

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);

    int x = nums1.size(), y = nums2.size();
    int low = 0, high = x;

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

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

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

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0)
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0;
            else
                return max(maxLeftX, maxLeftY);
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }
    return 0.0;
}

int main() {
    vector<int> nums1 = {1, 3};
    vector<int> nums2 = {2};
    cout << "Median is: " << findMedianSortedArrays(nums1, nums2) << endl;
    return 0;
}

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("Median is:", findMedianSortedArrays([1, 3], [2]))

public class MedianFinder {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length)
            return findMedianSortedArrays(nums2, nums1);

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

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

            int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];

            int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if ((x + y) % 2 == 0)
                    return ((double)Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
                else
                    return (double)Math.max(maxLeftX, maxLeftY);
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }
        return 0.0;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median is: " + findMedianSortedArrays(nums1, nums2));
    }
}

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

  let x = nums1.length, y = nums2.length;
  let low = 0, high = x;

  while (low <= high) {
    let partitionX = Math.floor((low + high) / 2);
    let partitionY = Math.floor((x + y + 1) / 2) - partitionX;

    let maxLeftX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1];
    let minRightX = (partitionX === x) ? Infinity : nums1[partitionX];

    let maxLeftY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1];
    let minRightY = (partitionY === y) ? Infinity : nums2[partitionY];

    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      if ((x + y) % 2 === 0)
        return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
      else
        return Math.max(maxLeftX, maxLeftY);
    } else if (maxLeftX > minRightY) {
      high = partitionX - 1;
    } else {
      low = partitionX + 1;
    }
  }
  return 0.0;
}

console.log("Median is:", findMedianSortedArrays([1, 3], [2]));

package main

import (
    "fmt"
    "math"
)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }
    x, y := len(nums1), len(nums2)
    low, high := 0, x

    for low <= high {
        px := (low + high) / 2
        py := (x + y + 1) / 2 - px

        maxLeftX := math.Inf(-1)
        if px != 0 {
            maxLeftX = float64(nums1[px-1])
        }
        minRightX := math.Inf(1)
        if px != x {
            minRightX = float64(nums1[px])
        }

        maxLeftY := math.Inf(-1)
        if py != 0 {
            maxLeftY = float64(nums2[py-1])
        }
        minRightY := math.Inf(1)
        if py != y {
            minRightY = float64(nums2[py])
        }

        if maxLeftX <= minRightY && maxLeftY <= minRightX {
            if (x+y)%2 == 0 {
                return (math.Max(maxLeftX, maxLeftY) + math.Min(minRightX, minRightY)) / 2
            }
            return math.Max(maxLeftX, maxLeftY)
        } else if maxLeftX > minRightY {
            high = px - 1
        } else {
            low = px + 1
        }
    }
    return 0.0
}

func main() {
    nums1 := []int{1, 3}
    nums2 := []int{2}
    fmt.Printf("Median is: %f\n", findMedianSortedArrays(nums1, nums2))
}

fn find_median_sorted_arrays(nums1: &Vec<i32>, nums2: &Vec<i32>) -> f64 {
    let (mut a, mut b) = (nums1, nums2);
    if a.len() > b.len() {
        return find_median_sorted_arrays(b, a);
    }

    let (x, y) = (a.len(), b.len());
    let (mut low, mut high) = (0, x);

    while low <= high {
        let partition_x = (low + high) / 2;
        let partition_y = (x + y + 1) / 2 - partition_x;

        let max_left_x = if partition_x == 0 { i32::MIN } else { a[partition_x - 1] };
        let min_right_x = if partition_x == x { i32::MAX } else { a[partition_x] };

        let max_left_y = if partition_y == 0 { i32::MIN } else { b[partition_y - 1] };
        let min_right_y = if partition_y == y { i32::MAX } else { b[partition_y] };

        if max_left_x <= min_right_y && max_left_y <= min_right_x {
            return if (x + y) % 2 == 0 {
                (max_left_x.max(max_left_y) as f64 + min_right_x.min(min_right_y) as f64) / 2.0
            } else {
                max_left_x.max(max_left_y) as f64
            };
        } else if max_left_x > min_right_y {
            high = partition_x - 1;
        } else {
            low = partition_x + 1;
        }
    }
    0.0
}

fn main() {
    let nums1 = vec![1, 3];
    let nums2 = vec![2];
    println!("Median is: {}", find_median_sorted_arrays(&nums1, &nums2));
}

fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    val (a, b) = if (nums1.size > nums2.size) nums2 to nums1 else nums1 to nums2
    val x = a.size
    val y = b.size
    var low = 0
    var high = x

    while (low <= high) {
        val px = (low + high) / 2
        val py = (x + y + 1) / 2 - px

        val maxLeftX = if (px == 0) Int.MIN_VALUE else a[px - 1]
        val minRightX = if (px == x) Int.MAX_VALUE else a[px]

        val maxLeftY = if (py == 0) Int.MIN_VALUE else b[py - 1]
        val minRightY = if (py == y) Int.MAX_VALUE else b[py]

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            return if ((x + y) % 2 == 0)
                (maxOf(maxLeftX, maxLeftY) + minOf(minRightX, minRightY)) / 2.0
            else
                maxOf(maxLeftX, maxLeftY).toDouble()
        } else if (maxLeftX > minRightY) {
            high = px - 1
        } else {
            low = px + 1
        }
    }
    return 0.0
}

fun main() {
    val nums1 = intArrayOf(1, 3)
    val nums2 = intArrayOf(2)
    println("Median is: ${findMedianSortedArrays(nums1, nums2)}")
}

func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
    let (a, b) = nums1.count > nums2.count ? (nums2, nums1) : (nums1, nums2)
    let x = a.count
    let y = b.count
    var low = 0
    var high = x

    while low <= high {
        let px = (low + high) / 2
        let py = (x + y + 1) / 2 - px

        let maxLeftX = px == 0 ? Int.min : a[px - 1]
        let minRightX = px == x ? Int.max : a[px]

        let maxLeftY = py == 0 ? Int.min : b[py - 1]
        let minRightY = py == y ? Int.max : b[py]

        if maxLeftX <= minRightY && maxLeftY <= minRightX {
            if (x + y) % 2 == 0 {
                return Double(max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
            } else {
                return Double(max(maxLeftX, maxLeftY))
            }
        } else if maxLeftX > minRightY {
            high = px - 1
        } else {
            low = px + 1
        }
    }
    return 0.0
}

let nums1 = [1, 3]
let nums2 = [2]
print("Median is:", findMedianSortedArrays(nums1, nums2))

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

    const x = nums1.length, y = nums2.length;
    let low = 0, high = x;

    while (low <= high) {
        const px = Math.floor((low + high) / 2);
        const py = Math.floor((x + y + 1) / 2) - px;

        const maxLeftX = (px === 0) ? -Infinity : nums1[px - 1];
        const minRightX = (px === x) ? Infinity : nums1[px];

        const maxLeftY = (py === 0) ? -Infinity : nums2[py - 1];
        const minRightY = (py === y) ? Infinity : nums2[py];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = px - 1;
        } else {
            low = px + 1;
        }
    }
    return 0.0;
}

console.log("Median is:", findMedianSortedArrays([1, 3], [2]));

Time complexity

Space complexity

O(1)

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