# 475. Heaters (M)

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range. 

Given the positions of `houses` and `heaters` on a horizontal line, return *the minimum radius standard of heaters so that those heaters could cover all houses.*

**Notice** that all the `heaters` follow your radius standard, and the warm radius will the same.

 

**Example 1:**

```
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
```

**Example 2:**

```
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.
```

**Example 3:**

```
Input: houses = [1,5], heaters = [2]
Output: 3
```

 

**Constraints:**

* `1 <= houses.length, heaters.length <= 3 * 104`
* `1 <= houses[i], heaters[i] <= 109`

### Solution:

先对于加热器数组排序。 对于每个房屋i，在加热器数组里使用二分查找找到距离房屋i最近的加热器的位置，最后的答案为所有房屋答案的最大值。

```
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int radius = 0;
        for(int i = 0; i< houses.length; i++)
        {
            radius  = Math.max(radius, findNearestHeater(houses[i], heaters) );
        }
        return radius;
        
    }
    
    public int findNearestHeater(int house, int[] heaters)
    {
        int start = 0;
        int end = heaters.length-1;
        while(start+1 < end)
        {
            int mid = start+(end-start)/2;
            if(heaters[mid] == house)
            {
                return 0;
            }
            else if(heaters[mid] > house)
            {
                end = mid;
            }
            else
            {
                start = mid;
            }
        }
        
        return Math.min(Math.abs(heaters[start]- house), Math.abs(heaters[end]- house));
    }
}
```