Amazon — Find Median of Two Sorted Arrays (Binary Search)

Problem (Amazon Hard)

Given two sorted arrays nums1 and nums2, return the median of the combined sorted array. Must run in O(log(m+n)) time.

Example:

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

Key Insight — Binary Search on Partition

Binary search on the smaller array to find partition point i (partition j determined by total):

nums1[0..i-1] and nums2[0..j-1] form the left half
Valid partition: nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]

Solutions

Python

def findMedianSortedArrays(nums1, nums2) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        maxL1 = float('-inf') if i == 0 else nums1[i-1]
        minR1 = float('inf') if i == m else nums1[i]
        maxL2 = float('-inf') if j == 0 else nums2[j-1]
        minR2 = float('inf') if j == n else nums2[j]
        if maxL1 <= minR2 and maxL2 <= minR1:
            if (m + n) % 2 == 1:
                return float(max(maxL1, maxL2))
            return (max(maxL1, maxL2) + min(minR1, minR2)) / 2.0
        elif maxL1 > minR2:
            hi = i - 1
        else:
            lo = i + 1
    return 0.0

JavaScript

function findMedianSortedArrays(A, B) {
    if(A.length>B.length)[A,B]=[B,A];
    const m=A.length,n=B.length;
    let lo=0,hi=m;
    while(lo<=hi){
        const i=(lo+hi)>>1, j=(m+n+1)/2-i|0;
        const mL1=i===0?-Infinity:A[i-1], mR1=i===m?Infinity:A[i];
        const mL2=j===0?-Infinity:B[j-1], mR2=j===n?Infinity:B[j];
        if(mL1<=mR2&&mL2<=mR1){
            return(m+n)%2===1?Math.max(mL1,mL2):(Math.max(mL1,mL2)+Math.min(mR1,mR2))/2;
        }else if(mL1>mR2)hi=i-1;else lo=i+1;
    }
}

Java

public double findMedianSortedArrays(int[] A, int[] B) {
    if(A.length>B.length){int[]t=A;A=B;B=t;}
    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 mL1=i==0?Integer.MIN_VALUE:A[i-1], mR1=i==m?Integer.MAX_VALUE:A[i];
        int mL2=j==0?Integer.MIN_VALUE:B[j-1], mR2=j==n?Integer.MAX_VALUE:B[j];
        if(mL1<=mR2&&mL2<=mR1) return(m+n)%2==1?Math.max(mL1,mL2):(Math.max(mL1,mL2)+(double)Math.min(mR1,mR2))/2;
        else if(mL1>mR2)hi=i-1;else lo=i+1;
    }
    return 0;
}

C++

#include <vector>
#include <climits>
using namespace std;
double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    if(A.size()>B.size())swap(A,B);
    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 mL1=i?A[i-1]:INT_MIN, mR1=i<m?A[i]:INT_MAX;
        int mL2=j?B[j-1]:INT_MIN, mR2=j<n?B[j]:INT_MAX;
        if(mL1<=mR2&&mL2<=mR1) return(m+n)%2?max(mL1,mL2):(max(mL1,mL2)+(double)min(mR1,mR2))/2;
        else if(mL1>mR2)hi=i-1;else lo=i+1;
    }
    return 0;
}

C

double findMedian(int* A, int m, int* B, int n) {
    if(m>n){int*t=A;A=B;B=t;int s=m;m=n;n=s;}
    int lo=0,hi=m;
    while(lo<=hi){
        int i=(lo+hi)/2,j=(m+n+1)/2-i;
        int mL1=i?A[i-1]:INT_MIN,mR1=i<m?A[i]:INT_MAX;
        int mL2=j?B[j-1]:INT_MIN,mR2=j<n?B[j]:INT_MAX;
        if(mL1<=mR2&&mL2<=mR1){int mx=mL1>mL2?mL1:mL2;if((m+n)%2)return mx;int mn=mR1<mR2?mR1:mR2;return(mx+mn)/2.0;}
        else if(mL1>mR2)hi=i-1;else lo=i+1;
    }
    return 0;
}

Complexity

Approach	Time	Space
Binary search	O(log(min(m,n)))	O(1)