Median of an array? Best solution to keep track of median

December 2, 2023

Numbers are randomly generated and stored into an expanding array. How do you keep track of the median?

Ideas:
Array
Binary Tree
Heap

>Solution :

There’s a wide variety of options for programming in general, but since we’re working with JS the straightforward way is to simply keep an array and insert elements in sorted order, something like:

class Median {
  arr = []
  insert(i) {
    let l = 0,
      r = this.arr.length
    while (l < r) {
      const m = (l + r) >>> 1
      if (this.arr[m] < i) l = m + 1
      else r = m
    }
    this.arr.splice(l, 0, i)
  }
  get median() {
    const mid = (this.arr.length / 2) | 0
    return this.arr.length ?
      this.arr[mid] : (this.arr[mid - 1] + this.arr[mid]) / 2
  }
}

const m = new Median;
[2, 8, 8, -2, 19].forEach(m.insert.bind(m))
console.log(m.median)