题目

题目来源：力扣（LeetCode）

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 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. // 思考，如何去查找最小路径
  2. // 实际上就是去，查找第一个大于等于X的位置，
  3. // 假设是房子X，供暖器是a1,a2,a3,a4,a5;a4是大于等于x的，那么前面的a3是小于x的
  4. // x是落在a3 和 a4中间的，相当于x落在了查找到位置和前一位的中间值
  5. // 那么我们只要判断，这两个值哪一个是距离x最近的就行了
  6. var findRadius = function (houses, heaters) {
  7.     heaters.sort((a, b) => a - b)
  8.     let ans = 0;
  9.     for (const x of houses) {//遍历每一个房子的位置
  10.         let j = binarySearch(heaters, x);//j是第一个大于等于房子位置的，这个二分模型0，1，前面是小于x的，后面的大于等于x的，找到大于等于x的
  11.         let a = Math.abs(heaters[j] - x);
  12.         let b = Math.abs(j ? x - heaters[j - 1] : a + 1);//j 位置前面有多少元素
  13.         ans = Math.max(ans, Math.min(a, b));//当前x的房子的供暖器的半径最近就是a,b之间的较小值
  14.     }
  15.     return ans;
  16. };
  17. var binarySearch = function (nums, x) {
  18.     let head = 0, tail = nums.length - 1, mid;
  19.     while (head < tail) {//当头尾坐标不重合
  20.         mid = (head + tail) >> 1;
  21.         if (nums[mid] >= x) tail = mid;//
  22.         else head = mid + 1;
  23.     }
  24.     return head;
  25. }
  26.     // 理解这个程序，有可能返回的是大于等于x的，有可能返回的是数组的最后一个
  27.     // 那么这个写法呢，就会在合法范围内，尽量返回大于等于X的位置，如果不能返回，就返回小于X的位置