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 * 104
• 1 <= houses[i], heaters[i] <= 109

 1 import java.lang.reflect.Array;
 2 import java.util.Arrays;
 3 
 4 public class FindRadius {
 5     public int findRadius(int[] houses, int[] heaters) {
 6         int MAX=-1;
 7         //二分查找排序
 8         Arrays.sort(heaters);
 9         //遍历所有房子节点，找到每一个节点最近的加热站的距离
10         //结果就是所有距离中最大的
11         for (int house : houses) {
12             int index = binsearch(heaters, house);
13             MAX = Math.max(Math.abs(heaters[index] - house), MAX);
14         }
15         return MAX;
16     }
17 
18     public int binsearch(int[] num,int target){
19         int l=0,r=num.length-1;
20         while (l<r){
21             int mid=(l+r)/2;
22             if (num[mid]==target){
23                 return mid;
24             }else if (num[mid]>target){
25                 //二分查找注意点，这里不减1为了找了当前下标大于目标值的点。
26                 r=mid;
27             }else if (num[mid]<target){
28                 l=mid+1;
29             }
30         }
31         if (l==0) return l;
32         //判断当前点和前面那个点哪个距离更近
33         int a=Math.abs(num[l-1]-target),b=Math.abs(num[l]-target);
34         return a<b?l-1:l;
35     }
36 
37     public static void main(String[] args) {
38         int[] he={282475249,622650073,984943658,144108930,470211272,101027544,457850878,458777923};
39         int[] h={823564440,115438165,784484492,74243042,114807987,137522503,441282327,16531729,823378840,143542612};
40         int[] a={1,5,7,10};
41         System.out.println(new FindRadius().binsearch(a,11));
42         System.out.println(new FindRadius().findRadius(he,h));
43     }
44 }