Median of Two Sorted Arrays

You're given two arrays nums1 and nums2, each sorted in non-decreasing order. Return the median of all their elements taken together.

If the combined length is odd, the median is the middle element of the merged order. If it's even, the median is the average of the two middle elements, which may not be a whole number.

Aim for O(log(m + n)) time, where m and n are the two lengths. Answers within 10⁻⁵ of the exact median are accepted.

The median splits the combined values into a left half and a right half of equal size (the left gets the extra one when the total is odd), with everything on the left ≤ everything on the right.

Picture that split as a cut through each array: take the first i elements of nums1 and the first j elements of nums2 as the left half. Since the left half has a fixed size, half = (m + n + 1) // 2, choosing i forces j = half - i. So there is really only one number to search for.

A cut is correct when nums1[i-1] ≤ nums2[j] and nums2[j-1] ≤ nums1[i]. If nums1[i-1] is too big, i is too far right; if nums2[j-1] is too big, i is too far left. That one-directional feedback is what makes binary search work. Search over the shorter array so j never goes out of range, and treat missing neighbors past either end as -∞ or +∞.

def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
        if left1 > right2:
            hi = i - 1
        elif left2 > right1:
            lo = i + 1
        else:
            if (m + n) % 2:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2
    return 0.0

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
  const m = nums1.length;
  const n = nums2.length;
  const half = Math.floor((m + n + 1) / 2);
  let lo = 0;
  let hi = m;
  while (lo <= hi) {
    const i = Math.floor((lo + hi) / 2);
    const j = half - i;
    const left1 = i > 0 ? nums1[i - 1] : -Infinity;
    const right1 = i < m ? nums1[i] : Infinity;
    const left2 = j > 0 ? nums2[j - 1] : -Infinity;
    const right2 = j < n ? nums2[j] : Infinity;
    if (left1 > right2) {
      hi = i - 1;
    } else if (left2 > right1) {
      lo = i + 1;
    } else {
      if ((m + n) % 2) return Math.max(left1, left2);
      return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
    }
  }
  return 0;
}

Start with the O(m + n) merge and say it's correct but doesn't meet the log bound. Then reframe: "the median is a cut that splits everything into two equal halves, and fixing the cut in one array fixes it in the other." Interviewers want to hear that reframing, because it's what turns a two-array problem into a one-variable binary search.

Write the four boundary values with sentinels before writing the search, and trace one odd and one even example, plus a case where one array is empty. Most failed attempts break on those edges, not on the main idea.