var MedianFinder = function() {
    this.arr = [];
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    // 修正1：right 应该初始化为 length，代表查找范围是 [0, length)
    let left = 0, right = this.arr.length; 
    
    // 修正2：标准的二分查找模板
    while(left < right){
        // 中点计算修正
        const mid = Math.floor((left + right) / 2);
        
        if(num < this.arr[mid]){
            right = mid;
        } else {
            // 修正3：防止死循环，左边界必须向右移动
            left = mid + 1;
        }
    }
    // left 就是最终应该插入的位置
    this.arr.splice(left, 0, num);
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    const len = this.arr.length;
    if(len % 2 === 1){
        return this.arr[Math.floor(len/2)];
    } else {
        return (this.arr[len/2 - 1] + this.arr[len/2]) / 2;
    }
};