#84 · Binary Search

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the two sorted arrays. The overall run time complexity should be O(log (m + n)).

HardLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sorted arrays and the k-th element

The median is the middle element (or the average of the two middle ones) of the merged order. Finding the k-th smallest of two sorted arrays needs no merge: compare the (k/2)-th elements of each and discard the smaller side's first k/2 items, which cannot contain the answer.

Memory layout

Two contiguous sorted arrays accessed by index only.

Operation	Cost
k-th smallest	O(log k)

Partition (cut) of both arrays

Split a at i and b at j so that the left parts hold half of all items and every left element is ≤ every right element. Then the median is built from the four values around the cuts: max(aLeft, bLeft) and min(aRight, bRight). Only i needs searching; j follows from i.

Memory layout

Just two indices, with ±∞ sentinels for cuts at the ends.

Operation	Cost
binary search over i	O(log min(m, n))

Why it fits

Sortedness lets you reason about order without moving data: a comparison of two elements rules out a whole block on one side.
Binary searching the cut of the shorter array halves the candidate range each step, giving O(log min(m, n)) and also guaranteeing j stays in range.
Sentinel values (−∞, +∞) turn all boundary cases (empty array, cut at an end) into the same comparisons as the general case.

Why alternatives degrade

Merging into a new array:: Correct but O(m + n) time and memory; the problem asks for logarithmic time.
Heaps for two halves (running median):: Designed for streams: O((m + n) log (m + n)) here, ignoring that the inputs are already sorted.
Binary search on the value range:: Possible (count items ≤ x in both arrays) but needs the value range and costs O(log(range) · log(m + n)).

Four approaches, from naive to production

1 · beginner

Merge both arrays, take the middle

time O(m + n)space O(m + n)

Merge the sorted arrays with two pointers into a new array, then read the middle element (or the average of the two middle ones).

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    vector<int> merged;
    size_t i = 0, j = 0;
    while (i < a.size() || j < b.size()) {
        if (j == b.size() || (i < a.size() && a[i] <= b[j])) merged.push_back(a[i++]);
        else merged.push_back(b[j++]);
    }
    int n = merged.size();
    if (n % 2 == 1) return merged[n >> 1];
    return ((double)merged[n / 2 - 1] + merged[n / 2]) / 2;
}

public double findMedianSortedArrays(int[] a, int[] b) {
    int[] merged = new int[a.length + b.length]; int size = 0;
    int i = 0, j = 0;
    while (i < a.length || j < b.length) {
        if (j == b.length || (i < a.length && a[i] <= b[j])) merged[size++] = a[i++];
        else merged[size++] = b[j++];
    }
    int n = size;
    if (n % 2 == 1) return merged[n >> 1];
    return ((double) merged[n / 2 - 1] + merged[n / 2]) / 2;
}

def find_median_sorted_arrays(a, b):
    merged = []
    i = j = 0
    while i < len(a) or j < len(b):
        if j == len(b) or (i < len(a) and a[i] <= b[j]):
            merged.append(a[i]); i += 1
        else:
            merged.append(b[j]); j += 1
    n = len(merged)
    if n % 2 == 1: return merged[n >> 1]
    return (merged[n // 2 - 1] + merged[n // 2]) / 2

function findMedianSortedArrays(a: number[], b: number[]): number {
  const merged: number[] = [];
  let i = 0, j = 0;
  while (i < a.length || j < b.length) {
    if (j === b.length || (i < a.length && a[i] <= b[j])) merged.push(a[i++]);
    else merged.push(b[j++]);
  }
  const n = merged.length;
  if (n % 2 === 1) return merged[n >> 1];
  return (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

Flaws & bottlenecks

Allocates a full merged array.
Linear time, not the logarithmic bound the problem asks for.
Touches every element when only the middle matters.

Interviewer cross-questions

Why does the median need the merged order?

Say: It is defined on the sorted combined sequence, whose middle element(s) are what we want.

How does the even case work?

Say: The median is the average of the two middle items, positions n / 2 − 1 and n / 2.

Do you need the whole merge?

Say: No: stop after (m + n) / 2 + 1 items; that removes the extra array.

2 · intermediate

Walk to the middle without storing

time O((m + n) / 2) = O(m + n)space O(1)

Run the same merge but keep only the last two items taken, and stop after (m + n) / 2 + 1 steps.

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    int total = a.size() + b.size();
    size_t i = 0, j = 0; int prev = 0, curr = 0;
    for (int step = 0; step <= total >> 1; step++) {
        prev = curr;
        if (i < a.size() && (j >= b.size() || a[i] <= b[j])) curr = a[i++];
        else curr = b[j++];
    }
    return total % 2 == 1 ? curr : ((double)prev + curr) / 2;
}

public double findMedianSortedArrays(int[] a, int[] b) {
    int total = a.length + b.length;
    int i = 0, j = 0, prev = 0, curr = 0;
    for (int step = 0; step <= total >> 1; step++) {
        prev = curr;
        if (i < a.length && (j >= b.length || a[i] <= b[j])) curr = a[i++];
        else curr = b[j++];
    }
    return total % 2 == 1 ? curr : ((double) prev + curr) / 2;
}

def find_median_sorted_arrays(a, b):
    total = len(a) + len(b)
    i = j = prev = curr = 0
    for step in range((total >> 1) + 1):
        prev = curr
        if i < len(a) and (j >= len(b) or a[i] <= b[j]):
            curr = a[i]; i += 1
        else:
            curr = b[j]; j += 1
    return curr if total % 2 == 1 else (prev + curr) / 2

function findMedianSortedArrays(a: number[], b: number[]): number {
  const total = a.length + b.length;
  let i = 0, j = 0, prev = 0, curr = 0;
  for (let step = 0; step <= total >> 1; step++) {
    prev = curr;
    if (i < a.length && (j >= b.length || a[i] <= b[j])) curr = a[i++];
    else curr = b[j++];
  }
  return total % 2 === 1 ? curr : (prev + curr) / 2;
}

Flaws & bottlenecks

Still linear in the input size.
Ignores that sorted input lets you skip large blocks.
Even/odd handling must track the previous item.

Interviewer cross-questions

Why keep prev?

Say: For an even total the median is the average of the two middle items, so you need the last two taken.

Could one array be empty?

Say: Yes: the condition j >= b.length (or i >= a.length) then forces all picks from the other array.

How do you reach O(log) time?

Say: Skip items in blocks: compare elements k/2 ahead and discard half of k each round.

3 · advanced

k-th smallest by discarding k/2 each round

time O(log(m + n))space O(1)

To find the k-th smallest of two sorted arrays, compare a[i + k/2 − 1] and b[j + k/2 − 1]; the smaller one's first k/2 items cannot hold the answer and are discarded, shrinking k by that many.

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    int total = a.size() + b.size();
    int na = a.size(), nb = b.size();
    function<int(int)> kth = [&](int k) -> int {
        int i = 0, j = 0;
        while (true) {
            if (i == na) return b[j + k - 1];
            if (j == nb) return a[i + k - 1];
            if (k == 1) return min(a[i], b[j]);
            int half = k >> 1;
            int ni = min(i + half, na) - 1;
            int nj = min(j + half, nb) - 1;
            if (a[ni] <= b[nj]) { k -= ni - i + 1; i = ni + 1; }
            else { k -= nj - j + 1; j = nj + 1; }
        }
    };
    if (total % 2 == 1) return kth((total + 1) >> 1);
    return ((double)kth(total >> 1) + kth((total >> 1) + 1)) / 2;
}

public double findMedianSortedArrays(int[] a, int[] b) {
    int total = a.length + b.length;
    if (total % 2 == 1) return kth(a, b, (total + 1) >> 1);
    return ((double) kth(a, b, total >> 1) + kth(a, b, (total >> 1) + 1)) / 2;
}
private int kth(int[] a, int[] b, int k) {
    int i = 0, j = 0;
    while (true) {
        if (i == a.length) return b[j + k - 1];
        if (j == b.length) return a[i + k - 1];
        if (k == 1) return Math.min(a[i], b[j]);
        int half = k >> 1;
        int ni = Math.min(i + half, a.length) - 1;
        int nj = Math.min(j + half, b.length) - 1;
        if (a[ni] <= b[nj]) { k -= ni - i + 1; i = ni + 1; }
        else { k -= nj - j + 1; j = nj + 1; }
    }
}

def find_median_sorted_arrays(a, b):
    total = len(a) + len(b)
    def kth(k):
        i = j = 0
        while True:
            if i == len(a): return b[j + k - 1]
            if j == len(b): return a[i + k - 1]
            if k == 1: return min(a[i], b[j])
            half = k >> 1
            ni = min(i + half, len(a)) - 1
            nj = min(j + half, len(b)) - 1
            if a[ni] <= b[nj]:
                k -= ni - i + 1; i = ni + 1
            else:
                k -= nj - j + 1; j = nj + 1
    if total % 2 == 1: return kth((total + 1) >> 1)
    return (kth(total >> 1) + kth((total >> 1) + 1)) / 2

function findMedianSortedArrays(a: number[], b: number[]): number {
  const total = a.length + b.length;
  const kth = (k: number): number => {
    let i = 0, j = 0;
    while (true) {
      if (i === a.length) return b[j + k - 1];
      if (j === b.length) return a[i + k - 1];
      if (k === 1) return Math.min(a[i], b[j]);
      const half = k >> 1;
      const ni = Math.min(i + half, a.length) - 1;
      const nj = Math.min(j + half, b.length) - 1;
      if (a[ni] <= b[nj]) { k -= ni - i + 1; i = ni + 1; }
      else { k -= nj - j + 1; j = nj + 1; }
    }
  };
  if (total % 2 === 1) return kth((total + 1) >> 1);
  return (kth(total >> 1) + kth((total >> 1) + 1)) / 2;
}

Flaws & bottlenecks

The even case calls kth twice.
Index clamping (min with array length) and the base cases are fiddly.
The discard argument needs care when k is odd.

Interviewer cross-questions

Why can the smaller side's first k/2 items be discarded?

Say: If a[ni] ≤ b[nj], then fewer than k items are smaller than a[ni] in total (at most (k/2 − 1) + (k/2 − 1)), so a[ni] and everything before it rank below the k-th smallest and can be discarded.

What are the base cases?

Say: One array exhausted (the answer is k − 1 steps into the other) or k = 1 (the smaller of the two heads).

How is this related to binary search?

Say: Each round halves k, the same logarithmic shrinking as binary search.

4 · expert

Binary search on the partition

time O(log min(m, n))space O(1)

Binary search the cut i in the shorter array; j = ⌈(m + n) / 2⌉ − i. A valid cut has aLeft ≤ bRight and bLeft ≤ aRight (with ±∞ at the ends); then the median comes from max(aLeft, bLeft) and min(aRight, bRight).

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    if (a.size() > b.size()) return findMedianSortedArrays(b, a);
    int m = a.size(), n = b.size();
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) >> 1;
        int j = ((m + n + 1) >> 1) - i;
        double aLeft = i == 0 ? -INFINITY : a[i - 1];
        double aRight = i == m ? INFINITY : a[i];
        double bLeft = j == 0 ? -INFINITY : b[j - 1];
        double bRight = j == n ? INFINITY : b[j];
        if (aLeft <= bRight && bLeft <= aRight) {
            double leftMax = max(aLeft, bLeft);
            if ((m + n) % 2 == 1) return leftMax;
            return (leftMax + min(aRight, bRight)) / 2;
        }
        if (aLeft > bRight) hi = i - 1;
        else lo = i + 1;
    }
    throw invalid_argument("inputs must be sorted");
}

public double findMedianSortedArrays(int[] a, int[] b) {
    if (a.length > b.length) return findMedianSortedArrays(b, a);
    int m = a.length, n = b.length;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) >> 1;
        int j = ((m + n + 1) >> 1) - i;
        double aLeft = i == 0 ? Double.NEGATIVE_INFINITY : a[i - 1];
        double aRight = i == m ? Double.POSITIVE_INFINITY : a[i];
        double bLeft = j == 0 ? Double.NEGATIVE_INFINITY : b[j - 1];
        double bRight = j == n ? Double.POSITIVE_INFINITY : b[j];
        if (aLeft <= bRight && bLeft <= aRight) {
            double leftMax = Math.max(aLeft, bLeft);
            if ((m + n) % 2 == 1) return leftMax;
            return (leftMax + Math.min(aRight, bRight)) / 2;
        }
        if (aLeft > bRight) hi = i - 1;
        else lo = i + 1;
    }
    throw new IllegalArgumentException("inputs must be sorted");
}

def find_median_sorted_arrays(a, b):
    if len(a) > len(b): return find_median_sorted_arrays(b, a)
    m, n = len(a), len(b)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) >> 1
        j = ((m + n + 1) >> 1) - i
        a_left = float('-inf') if i == 0 else a[i - 1]
        a_right = float('inf') if i == m else a[i]
        b_left = float('-inf') if j == 0 else b[j - 1]
        b_right = float('inf') if j == n else b[j]
        if a_left <= b_right and b_left <= a_right:
            left_max = max(a_left, b_left)
            if (m + n) % 2 == 1: return left_max
            return (left_max + min(a_right, b_right)) / 2
        if a_left > b_right: hi = i - 1
        else: lo = i + 1
    raise ValueError('inputs must be sorted')

function findMedianSortedArrays(a: number[], b: number[]): number {
  if (a.length > b.length) return findMedianSortedArrays(b, a);
  const m = a.length, n = b.length;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = ((m + n + 1) >> 1) - i;
    const aLeft = i === 0 ? -Infinity : a[i - 1];
    const aRight = i === m ? Infinity : a[i];
    const bLeft = j === 0 ? -Infinity : b[j - 1];
    const bRight = j === n ? Infinity : b[j];
    if (aLeft <= bRight && bLeft <= aRight) {
      const leftMax = Math.max(aLeft, bLeft);
      if ((m + n) % 2 === 1) return leftMax;
      return (leftMax + Math.min(aRight, bRight)) / 2;
    }
    if (aLeft > bRight) hi = i - 1;
    else lo = i + 1;
  }
  throw new Error('inputs must be sorted');
}

Flaws & bottlenecks

Subtle boundary handling (empty array, cut at either end) relies on ±∞ sentinels.
Requires the shorter array on the search side so that j is never negative.
Hard to derive from scratch under interview pressure.

Interviewer cross-questions

Why search on the shorter array?

Say: It keeps j = ⌈(m + n)/2⌉ − i within 0 … n, and makes the search cost log of the smaller size.

What if both arrays contain duplicates?

Say: The ≤ comparisons accept equal values, so ties are fine.

What if the inputs might be unsorted?

Say: The algorithm is only correct for sorted input; here it throws if no valid cut exists, which signals bad input. Sorting first would cost O((m + n) log(m + n)).

Synchronized code walkthrough

Showing: Merge both arrays, take the middle — shares the player above; click any step to jump.

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    vector<int> merged;
    size_t i = 0, j = 0;
    while (i < a.size() || j < b.size()) {
        if (j == b.size() || (i < a.size() && a[i] <= b[j])) merged.push_back(a[i++]);
        else merged.push_back(b[j++]);
    }
    int n = merged.size();
    if (n % 2 == 1) return merged[n >> 1];
    return ((double)merged[n / 2 - 1] + merged[n / 2]) / 2;
}

public double findMedianSortedArrays(int[] a, int[] b) {
    int[] merged = new int[a.length + b.length]; int size = 0;
    int i = 0, j = 0;
    while (i < a.length || j < b.length) {
        if (j == b.length || (i < a.length && a[i] <= b[j])) merged[size++] = a[i++];
        else merged[size++] = b[j++];
    }
    int n = size;
    if (n % 2 == 1) return merged[n >> 1];
    return ((double) merged[n / 2 - 1] + merged[n / 2]) / 2;
}

def find_median_sorted_arrays(a, b):
    merged = []
    i = j = 0
    while i < len(a) or j < len(b):
        if j == len(b) or (i < len(a) and a[i] <= b[j]):
            merged.append(a[i]); i += 1
        else:
            merged.append(b[j]); j += 1
    n = len(merged)
    if n % 2 == 1: return merged[n >> 1]
    return (merged[n // 2 - 1] + merged[n // 2]) / 2

function findMedianSortedArrays(a: number[], b: number[]): number {
  const merged: number[] = [];
  let i = 0, j = 0;
  while (i < a.length || j < b.length) {
    if (j === b.length || (i < a.length && a[i] <= b[j])) merged.push(a[i++]);
    else merged.push(b[j++]);
  }
  const n = merged.length;
  if (n % 2 === 1) return merged[n >> 1];
  return (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    int total = a.size() + b.size();
    size_t i = 0, j = 0; int prev = 0, curr = 0;
    for (int step = 0; step <= total >> 1; step++) {
        prev = curr;
        if (i < a.size() && (j >= b.size() || a[i] <= b[j])) curr = a[i++];
        else curr = b[j++];
    }
    return total % 2 == 1 ? curr : ((double)prev + curr) / 2;
}

public double findMedianSortedArrays(int[] a, int[] b) {
    int total = a.length + b.length;
    int i = 0, j = 0, prev = 0, curr = 0;
    for (int step = 0; step <= total >> 1; step++) {
        prev = curr;
        if (i < a.length && (j >= b.length || a[i] <= b[j])) curr = a[i++];
        else curr = b[j++];
    }
    return total % 2 == 1 ? curr : ((double) prev + curr) / 2;
}

def find_median_sorted_arrays(a, b):
    total = len(a) + len(b)
    i = j = prev = curr = 0
    for step in range((total >> 1) + 1):
        prev = curr
        if i < len(a) and (j >= len(b) or a[i] <= b[j]):
            curr = a[i]; i += 1
        else:
            curr = b[j]; j += 1
    return curr if total % 2 == 1 else (prev + curr) / 2

function findMedianSortedArrays(a: number[], b: number[]): number {
  const total = a.length + b.length;
  let i = 0, j = 0, prev = 0, curr = 0;
  for (let step = 0; step <= total >> 1; step++) {
    prev = curr;
    if (i < a.length && (j >= b.length || a[i] <= b[j])) curr = a[i++];
    else curr = b[j++];
  }
  return total % 2 === 1 ? curr : (prev + curr) / 2;
}

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    int total = a.size() + b.size();
    int na = a.size(), nb = b.size();
    function<int(int)> kth = [&](int k) -> int {
        int i = 0, j = 0;
        while (true) {
            if (i == na) return b[j + k - 1];
            if (j == nb) return a[i + k - 1];
            if (k == 1) return min(a[i], b[j]);
            int half = k >> 1;
            int ni = min(i + half, na) - 1;
            int nj = min(j + half, nb) - 1;
            if (a[ni] <= b[nj]) { k -= ni - i + 1; i = ni + 1; }
            else { k -= nj - j + 1; j = nj + 1; }
        }
    };
    if (total % 2 == 1) return kth((total + 1) >> 1);
    return ((double)kth(total >> 1) + kth((total >> 1) + 1)) / 2;
}

public double findMedianSortedArrays(int[] a, int[] b) {
    int total = a.length + b.length;
    if (total % 2 == 1) return kth(a, b, (total + 1) >> 1);
    return ((double) kth(a, b, total >> 1) + kth(a, b, (total >> 1) + 1)) / 2;
}
private int kth(int[] a, int[] b, int k) {
    int i = 0, j = 0;
    while (true) {
        if (i == a.length) return b[j + k - 1];
        if (j == b.length) return a[i + k - 1];
        if (k == 1) return Math.min(a[i], b[j]);
        int half = k >> 1;
        int ni = Math.min(i + half, a.length) - 1;
        int nj = Math.min(j + half, b.length) - 1;
        if (a[ni] <= b[nj]) { k -= ni - i + 1; i = ni + 1; }
        else { k -= nj - j + 1; j = nj + 1; }
    }
}

def find_median_sorted_arrays(a, b):
    total = len(a) + len(b)
    def kth(k):
        i = j = 0
        while True:
            if i == len(a): return b[j + k - 1]
            if j == len(b): return a[i + k - 1]
            if k == 1: return min(a[i], b[j])
            half = k >> 1
            ni = min(i + half, len(a)) - 1
            nj = min(j + half, len(b)) - 1
            if a[ni] <= b[nj]:
                k -= ni - i + 1; i = ni + 1
            else:
                k -= nj - j + 1; j = nj + 1
    if total % 2 == 1: return kth((total + 1) >> 1)
    return (kth(total >> 1) + kth((total >> 1) + 1)) / 2

function findMedianSortedArrays(a: number[], b: number[]): number {
  const total = a.length + b.length;
  const kth = (k: number): number => {
    let i = 0, j = 0;
    while (true) {
      if (i === a.length) return b[j + k - 1];
      if (j === b.length) return a[i + k - 1];
      if (k === 1) return Math.min(a[i], b[j]);
      const half = k >> 1;
      const ni = Math.min(i + half, a.length) - 1;
      const nj = Math.min(j + half, b.length) - 1;
      if (a[ni] <= b[nj]) { k -= ni - i + 1; i = ni + 1; }
      else { k -= nj - j + 1; j = nj + 1; }
    }
  };
  if (total % 2 === 1) return kth((total + 1) >> 1);
  return (kth(total >> 1) + kth((total >> 1) + 1)) / 2;
}

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    if (a.size() > b.size()) return findMedianSortedArrays(b, a);
    int m = a.size(), n = b.size();
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) >> 1;
        int j = ((m + n + 1) >> 1) - i;
        double aLeft = i == 0 ? -INFINITY : a[i - 1];
        double aRight = i == m ? INFINITY : a[i];
        double bLeft = j == 0 ? -INFINITY : b[j - 1];
        double bRight = j == n ? INFINITY : b[j];
        if (aLeft <= bRight && bLeft <= aRight) {
            double leftMax = max(aLeft, bLeft);
            if ((m + n) % 2 == 1) return leftMax;
            return (leftMax + min(aRight, bRight)) / 2;
        }
        if (aLeft > bRight) hi = i - 1;
        else lo = i + 1;
    }
    throw invalid_argument("inputs must be sorted");
}

public double findMedianSortedArrays(int[] a, int[] b) {
    if (a.length > b.length) return findMedianSortedArrays(b, a);
    int m = a.length, n = b.length;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) >> 1;
        int j = ((m + n + 1) >> 1) - i;
        double aLeft = i == 0 ? Double.NEGATIVE_INFINITY : a[i - 1];
        double aRight = i == m ? Double.POSITIVE_INFINITY : a[i];
        double bLeft = j == 0 ? Double.NEGATIVE_INFINITY : b[j - 1];
        double bRight = j == n ? Double.POSITIVE_INFINITY : b[j];
        if (aLeft <= bRight && bLeft <= aRight) {
            double leftMax = Math.max(aLeft, bLeft);
            if ((m + n) % 2 == 1) return leftMax;
            return (leftMax + Math.min(aRight, bRight)) / 2;
        }
        if (aLeft > bRight) hi = i - 1;
        else lo = i + 1;
    }
    throw new IllegalArgumentException("inputs must be sorted");
}

def find_median_sorted_arrays(a, b):
    if len(a) > len(b): return find_median_sorted_arrays(b, a)
    m, n = len(a), len(b)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) >> 1
        j = ((m + n + 1) >> 1) - i
        a_left = float('-inf') if i == 0 else a[i - 1]
        a_right = float('inf') if i == m else a[i]
        b_left = float('-inf') if j == 0 else b[j - 1]
        b_right = float('inf') if j == n else b[j]
        if a_left <= b_right and b_left <= a_right:
            left_max = max(a_left, b_left)
            if (m + n) % 2 == 1: return left_max
            return (left_max + min(a_right, b_right)) / 2
        if a_left > b_right: hi = i - 1
        else: lo = i + 1
    raise ValueError('inputs must be sorted')

function findMedianSortedArrays(a: number[], b: number[]): number {
  if (a.length > b.length) return findMedianSortedArrays(b, a);
  const m = a.length, n = b.length;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = ((m + n + 1) >> 1) - i;
    const aLeft = i === 0 ? -Infinity : a[i - 1];
    const aRight = i === m ? Infinity : a[i];
    const bLeft = j === 0 ? -Infinity : b[j - 1];
    const bRight = j === n ? Infinity : b[j];
    if (aLeft <= bRight && bLeft <= aRight) {
      const leftMax = Math.max(aLeft, bLeft);
      if ((m + n) % 2 === 1) return leftMax;
      return (leftMax + Math.min(aRight, bRight)) / 2;
    }
    if (aLeft > bRight) hi = i - 1;
    else lo = i + 1;
  }
  throw new Error('inputs must be sorted');
}