# Heaters

`Binary Search`

## Solution & Analysis

Via [@yhteng](https://www.lintcode.com/user/yhteng/)

这题主要有两个点：

第一个是如何确定离某一个house最近的heater并记录它们之间的距离，这些距离所构成的集合中的最大值就是答案。从算法上来看，比较合理的做法是遍历houses集合，并找到每一个house对应最近的heater以及它们之间的距离，所以本质上是针对每个house，找到其在heaters数组中的插入位置，变成了insert into an sorted array的问题。

第二个是插入排序数组的问题，如果逐个遍历heaters中的每个元素（包括双指针），那么复杂度是o(n)，这里可以采用二分法来查找，进而得到o(logn)的复杂度。

给定每个house 位置找到离他最近的heater，然后求出该radius。将所有的radius求个最大值即为结果。

在对每个house找closest heater时，利用二分法。先sort heater，然后在该heater中找到和house pos 最接近的值即为最小radius。

Via @[shawngao](https://leetcode.com/shawngao)

The idea is to leverage decent`Arrays.binarySearch()`function provided by Java.\
1\. For each `house`, find its position between those `heaters`(thus we need the `heaters`array to be sorted).\
2\. Calculate the distances between this `house` and left `heater` and right `heater`, get a `MIN` value of those two values. Corner cases are there is no left or right heater.\
3\. Get `MAX` value among distances in step 2. It's the answer.

Time complexity: max(O(nlogn), O(mlogn)) - m is the length of houses, n is the length of heaters.

### Binary Search + Loop

这里的Binary Search也可以使用Arrays.binarySearch(int\[] a, t); 但是要处理返回的index，index可能为-1.

```java
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int radius = Integer.MIN_VALUE;

        for (int house: houses) {
            int index = binarySearch(heaters, house);
            int distLeft = index >= 1 ? house - heaters[index - 1] : Integer.MAX_VALUE;
            int distRight = index < heaters.length ? heaters[index] - house: Integer.MAX_VALUE;
            radius = Math.max(Math.min(distLeft, distRight), radius);    
        }
        return radius;
    }

    private int binarySearch(int[] heaters, int house) {
        int lo = 0; 
        int hi = heaters.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (heaters[mid] == house) {
                return mid;
            } else if (heaters[mid] < house) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return lo;
    }
}
```

## Reference

<https://leetcode.com/problems/heaters/discuss/95886/Short-and-Clean-Java-Binary-Search-Solution>