475. 供暖器

首先想到的就是找到所有距离房屋最短距离的heater的距离 r ，然后返回最大的 r

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
};

既然这样，那么也可以利用二分法找到heater

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
};