[475] 供暖器

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 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 <= houses.length, heaters.length <= 3 * 10
• 1 <= houses[i], heaters[i] <= 10

<br />

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        //找到每个房屋位置所需要的最小半径的最大值
        int res = 0;
        int n = heaters.size();
        sort(heaters.begin(), heaters.end());
        for (auto house : houses)
        {
            //二分法找不小于house的第一个值
            int left = 0, right = n;
            while (left < right)
            {
                int mid = left + (right - left)/2;
                if (house > heaters[mid]) left = mid + 1;
                else right = mid;
            }
            int dist1 = (right == 0) ? INT_MAX : abs(house - heaters[right - 1]);
            int dist2 = (right == n) ? INT_MAX : abs(house - heaters[right]);
            res = max(res, min(dist1, dist2));
        }
        return res;
    }
};