475-供暖器

var findRadius = function(houses, heaters) {
    var max = 0    for(let i = 0 ; i < houses.length ; i ++) {
        var house_position = houses[i]
        var r = Infinity        for(let j = 0 ; j < heaters.length ; j ++) {
            var heat_position = heaters[j]
            var reduce = Math.abs(house_position - heat_position)
            r = Math.min(r,reduce)
        }
        max = Math.max(r,max)
    }
    return max
};

var findRadius = function(houses, heaters) {
    var r = 0    for(let i = 0 ; i < houses.length ; i ++) {
        var house_position = houses[i]
        let left = 0 , right = heaters.length - 1        //  查找离 house_position 最近的 heat_position        //  也就是查找 house_position 的最右插入点        while(left <= right && right < heaters.length) {
            let mid = left + Math.floor((right - left) / 2)
            var heat_position = heaters[mid]
            // 找到的不大于，再往右边找            if(heat_position <=  house_position) {
                left = mid + 1            } else {
                right = mid - 1            }
        }
        // 这时候找到的插入点不一定是最近的,左边的比他小，所以需要比较一下        var  R = Math.abs(heaters[right] - house_position)
        if(right > 0) {
            R = Math.min( Math.abs( heaters[right - 1] - house_position) , R)
        }
        r = Math.max(r,R)
    }
    return r
};