Heaps: Find the Running Median

running-median.js

// https://www.hackerrank.com/challenges/ctci-find-the-running-median

let input = `6
12
4
5
3
8
7`;

function locationOf(item, array, first=0, last=array.length) {
    let pivot = parseInt(first + (last-first) / 2);

    if(array[pivot] === item) {
        return pivot;
    }
    if(last-first <= 1) {
        return array[pivot] > item ? pivot-1 : pivot;
    }
    if(array[pivot] < item) {
        return locationOf(item, array, pivot, last);
    }else {
        return locationOf(item, array, first, pivot);
    }
}


function MedianMonster() {
    this.values = [];
}

MedianMonster.prototype.add = function(value) {
    this.values.splice(locationOf(value, this.values)+1, 0, value);
}

MedianMonster.prototype.median = function() {
    let len = this.values.length;
    if(len === 1) {
        return this.values[0];
    }

    let middle = Math.ceil(len / 2)-1;

    if(len % 2 === 0) { //average two middle values
        let values = [middle, middle+1].map(idx => this.values[idx]);
        return (values[0] + values[1]) / 2;
    }else {
        return this.values[middle];
    }

}

MedianMonster.prototype.process = function(value) {
    this.add(value);
    return this.median();
}

let monster = new MedianMonster();

input.split('\n').slice(1).map(value => parseInt(value, 10)).forEach(value => {
    console.log(monster.process(value).toFixed(1));
});