Найти медиану объединения двух отсортированных массивов

Условие

Имеются два отсортированных массива чисел a и b длиной lenA и lenB соответственно. Требуется определить медиану массива, полученного при слиянии всех элементов этих двух массивов.

Ответ

Можно пройти два отсортированных массива двумя указателями только до середины общего порядка. Полный объединённый массив создавать не требуется.

function median(a, b) {
  const total = a.length + b.length;
  if (total === 0) throw new RangeError('Оба массива пусты');
  let i = 0, j = 0, previous, current;
  for (let step = 0; step <= Math.floor(total / 2); step++) {
    previous = current;
    if (j === b.length || (i < a.length && a[i] <= b[j])) current = a[i++];
    else current = b[j++];
  }
  return total % 2 ? current : previous / 2 + current / 2;
}

Предполагаются конечные числа и сортировка по возрастанию. Время O(m+n), память O(1); если требуется логарифмическое время, применяют бинарный поиск границы разбиения.