Problem

Given a stream of integers, find the median of the stream at any given point.
Example input: [2, 1, 5, 7, 2, 0, 5]
Example output: [2, 1.5, 2, 3.5, 2, 2, 2]

Solution

// Solution:
// The median of a set of numbers is the middle number when the numbers are sorted.
// To find the median of a stream of numbers, we can keep track of the numbers in a sorted array.
// When a new number is added, we can insert it into the array in the correct position.
// This will take O(n) time, but we can use a binary search to find the correct position,
// which will take O(log n) time.
// The median is the middle number in the array, so we can find it in O(1) time.
// The total time complexity is O(log n).

function medianStream(stream) {
  const sorted = [];
  const medians = [];

  for (let i = 0; i < stream.length; i++) {
    const num = stream[i];
    const index = binarySearch(sorted, num);
    sorted.splice(index, 0, num);
    medians.push(getMedian(sorted));
  }

  return medians;
}

function binarySearch(arr, num) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    if (arr[mid] === num) {
      return mid;
    } else if (arr[mid] < num) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }

  return start;
}

function getMedian(arr) {
  const mid = Math.floor(arr.length / 2);

  if (arr.length % 2 === 0) {
    return (arr[mid - 1] + arr[mid]) / 2;
  } else {
    return arr[mid];
  }
}

console.log(medianStream([2, 1, 5, 7, 2, 0, 5])); // [2, 1.5, 2, 3.5, 2, 2, 2]