题目
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: houses = [1,2,3], heaters = [2] 输出: 1 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:
输入: houses = [1,2,3,4], heaters = [1,4] 输出: 1 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
示例 3：
输入：houses = [1,5], heaters = [2] 输出：3
解题
方法一：排序+二分查找
遍历每个房屋，利用二分查找，查找离这个房屋最近的取暖器。取最大的距离为结果。
1.房子位置 比 所有取暖器位置 都要小(index=0)，求房子与最左边的取暖器的距离
2.房子位置 比 所有取暖器位置 都要大(index=heater.size()),求房子与最右边取暖器的距离
3.房子位置 在取暖器们 中间， 求与房子左侧和右侧取暖器距离的最小值。
class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters) { sort(houses.begin(),houses.end()); sort(heaters.begin(),heaters.end()); int res=0; for(int house:houses){ res=max(res,distance(house,heaters)); } return res; } int distance(int house,vector<int>& heaters){ if(heaters.size()==1) return abs(house-heaters[0]); int index=lower_bound(heaters.begin(),heaters.end(),house)-heaters.begin(); if(index==0) return abs(house-heaters[0]); if(index==heaters.size()) return abs(house-heaters.back()); return min(abs(house-heaters[index-1]),abs(house-heaters[index])); } };
