475.供暖器.md

方法一：二分+双指针。

二分，给谁二分？当然是给半径二分，将二分求得的半径进行检验，判断使用这个半径是否能让所有房屋都能得到供暖。

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        int res = 1;
        Arrays.sort(heaters);
        Arrays.sort(houses);
        int left = 0, right = (int)1e9;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(houses, heaters, mid)) right = mid;
            else left = mid + 1;
        }
        return right;
    }

    public boolean check(int[] houses, int[] heaters, int x) {
        int n = houses.length, m = heaters.length;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < m && houses[i] > heaters[j] + x) j++;
            if (j < m && heaters[j] - x <= houses[i] && houses[i] <= heaters[j] + x) continue;
            return false;
        }
        return true;
    }
}

二分的模板

int left = 0, right = ①...;
while (left < right) { // ②
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        //... ③
    } else if (nums[mid] > target) {
        right = ...; ④
    } else if (nums[mid] < target) {
        left = ...; ⑤
    }
}

②这里要不要写等于号，也就是 left < right 或者 left <= right ，取决于我们二分时采用什么样的范围模型，如果采用前者那就是前闭后开的区间范围，如果是后者则采用两边都闭的区间范围模型。

如果采用前闭后开的范围模型，那么①就是right = nums.length，而④这个位置就是right = mid，因为mid的值是不能取的；如果采用前后都闭的区间模型，那么①就是nums.length - 1，④就是right = mid - 1，因为这时候如果采用right = mid会取到mid的值。

二分的各种细节资料总结：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/