Median of Two Sorted Arrays

hard binary search partition

Problem

Given two sorted arrays A and B of sizes m and n, return the median of the combined sorted sequence in O(log min(m, n)).

InputA = [1,3], B = [2]

Output2.0

Pick a cut i in A and j = (m+n+1)/2 − i in B. The cut is correct when A[i−1] ≤ B[j] and B[j−1] ≤ A[i]. Binary-search i in the smaller array.

A (sorted)

B (sorted)

def find_median(A, B):
    if len(A) > len(B): A, B = B, A
    m, n = len(A), len(B)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - 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 float(max(aL, bL))
            return (max(aL, bL) + min(aR, bR)) / 2.0
        if aL > bR: hi = i - 1
        else: lo = i + 1

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

class Solution {
    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, half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2, j = half - i;
            int aL = i > 0 ? A[i-1] : Integer.MIN_VALUE;
            int aR = i < m ? A[i]   : Integer.MAX_VALUE;
            int bL = j > 0 ? B[j-1] : Integer.MIN_VALUE;
            int bR = j < n ? B[j]   : Integer.MAX_VALUE;
            if (aL <= bR && bL <= aR) {
                if (((m + n) & 1) == 1) return Math.max(aL, bL);
                return (Math.max(aL, bL) + Math.min(aR, bR)) / 2.0;
            }
            if (aL > bR) hi = i - 1; else lo = i + 1;
        }
        return 0.0;
    }
}

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

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