# Heaters

`Binary Search`

## Solution & Analysis

Via @yhteng

Via @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

``````class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);

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;
}
}

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