Median of Two Sorted Arrays [Hard] — Binary Search on Partition

Problem Statement

Given two sorted arrays, return the median of the two sorted arrays. Overall run time must be O(log(m+n)).

Input: nums1=[1,3], nums2=[2] → Output: 2.0
Input: nums1=[1,2], nums2=[3,4] → Output: 2.5

Intuition

Binary search on the smaller array for a partition point i such that elements left of i in nums1 and left of corresponding j in nums2 form the correct left half. Check that max-left ≤ min-right.

Solutions

C++

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    if (A.size()>B.size()) return findMedianSortedArrays(B,A);
    int m=A.size(), n=B.size(), lo=0, hi=m;
    while (lo<=hi) {
        int i=(lo+hi)/2, j=(m+n+1)/2-i;
        int Aleft=i?A[i-1]:INT_MIN, Aright=i<m?A[i]:INT_MAX;
        int Bleft=j?B[j-1]:INT_MIN, Bright=j<n?B[j]:INT_MAX;
        if(Aleft<=Bright&&Bleft<=Aright) {
            if((m+n)%2) return max(Aleft,Bleft);
            return (max(Aleft,Bleft)+min(Aright,Bright))/2.0;
        } else if(Aleft>Bright) hi=i-1;
        else lo=i+1;
    }
    return 0;
}

Java

public double findMedianSortedArrays(int[] A, int[] B) {
    if (A.length>B.length) return findMedianSortedArrays(B,A);
    int m=A.length, n=B.length, lo=0, hi=m;
    while (lo<=hi) {
        int i=(lo+hi)/2, j=(m+n+1)/2-i;
        int Al=i>0?A[i-1]:Integer.MIN_VALUE, Ar=i<m?A[i]:Integer.MAX_VALUE;
        int Bl=j>0?B[j-1]:Integer.MIN_VALUE, Br=j<n?B[j]:Integer.MAX_VALUE;
        if(Al<=Br&&Bl<=Ar){
            if((m+n)%2==1) return Math.max(Al,Bl);
            return (Math.max(Al,Bl)+Math.min(Ar,Br))/2.0;
        } else if(Al>Br) hi=i-1;
        else lo=i+1;
    }
    return 0;
}

Python

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    A, B = nums1, nums2
    if len(A) > len(B):
        A, B = B, A
    m, n = len(A), len(B)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        Al = A[i-1] if i > 0 else float('-inf')
        Ar = A[i]   if i < m else float('inf')
        Bl = B[j-1] if j > 0 else float('-inf')
        Br = B[j]   if j < n else float('inf')
        if Al <= Br and Bl <= Ar:
            if (m + n) % 2:
                return max(Al, Bl)
            return (max(Al, Bl) + min(Ar, Br)) / 2.0
        elif Al > Br:
            hi = i - 1
        else:
            lo = i + 1
    return 0.0

Complexity

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