## Description

https://leetcode.com/problems/heaters/

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:1Explanation: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:1Explanation: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 * 10`

^{4}`1 <= houses[i], heaters[i] <= 10`

^{9}

## Python Solution

Use binary search to find the max distance between all closest pairs of house and heater.

```
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
heaters.sort()
min_heat_radius = 0
for house in houses:
radius = self.get_min_heat_radius(house, heaters)
min_heat_radius = max(min_heat_radius, radius)
return min_heat_radius
def get_min_heat_radius(self, house, heaters):
left = 0
right = len(heaters) - 1
while left + 1 < right:
mid = left + (right - left) // 2
if heaters[mid] <= house:
left = mid
else:
right = mid
return min(abs(heaters[left] - house), abs(heaters[right] - house))
```

- Time Complexity: O(MlogM + NlogM), M is the number of heaters, N is the number of houses.
- Space Complexity: O(1).