算法随笔_10: 供暖器
上一篇：算法随笔_9:压缩字符串-CSDN博客
题目描述如下：
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: houses = [1,2,3], heaters = [2] 输出: 1 解释: 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。
算法思路:
题目要求我们求出最小的加热半径来为所有的房屋供暖。因此，每个房屋要尽可能的离供暖器近。换句话说，每个房屋要找到离它最近的那个供暖器，并计算出距离，我们可以设一个数组heat_near。最后取这个数组的最大值就是本题的答案。
一般对于在数组里查找某个特定条件下的值的情况，我们优先想到的就是二分查找，也叫折半查找。二分查找的前提需要这个数组是有序的。所以我们先把heaters数组进行一下升序排列。
接下来我们需要先找到紧邻房屋house左侧的那个供暖器，我们设它的下标为heat_near_left。
算法如下:
1. 我们计算出供暖器数组中间位置的暖器位置heat_mid。
2. 如果heat_mid小于house，意味着我们需要在右半个区间继续寻找紧邻房屋house左侧的那个暖器。重复步骤1，2。如果heat_mid大于house，我们需要在左半个区间重复步骤1，2。注意：步骤1中的暖气数组此时变为左半区间，或右半区间。
3. 持续折半后，最终会找到紧邻房屋house左侧的那个暖器的下标heat_near_left。
那么紧邻房屋house右侧的那个暖器的下标为即为heat_near_left+1。分别计算这两个下标的元素到当前house的距离dist_left, dist_right。最终，当前房屋最近的供暖器的距离为min(dist_left, dist_right)。
当得出全部房屋最近的供暖器的距离时，取最大值即为题目的答案。