# Easy to understand C++ solution with vanilla binary search & STL lower_bound

• Well the idea is same as most of the other solutions.

1. Sort the heater array
2. For each house, get its left and right bounds 'pair' from the heaters array. For each house take the min of the pair(because the the closest heater is sufficient to heat the house, other heater can be discarded). Maximize this value for all houses.
``````class Solution {
public:
pair<int,int> binsearch(int key, vector<int> &v) {
//skip searching the array if the key is out of bounds
if(key < v[0])
return make_pair(INT_MAX, v[0] - key);
else if(key > v.back())
return make_pair(key - v.back(), INT_MAX);
//else search
int l = 0, r = v.size() - 1;
while(l < r) {
int m = l + ((r-l) >> 1);
if(key > v[m])
l = m + 1;
else
r = m;
}
return v[l] == key ? make_pair(0,0) : make_pair(key - v[l-1], v[l] - key);
}
int findRadius(vector<int>& houses, vector<int>& heaters) {
//if there is no house
if(!houses.size())
return 0;
//if there is no heater
if(!heaters.size())
return INT_MAX;
sort(heaters.begin(), heaters.end());
int ret = 0;
for(auto h : houses) {
auto lr = binsearch(h, heaters);
ret = max(ret, min(lr.first, lr.second));

/*remove this comment & comment out previous two lines if using library function is preferred(it takes more time)
auto lb = lower_bound(heaters.begin(), heaters.end(), h);
if(lb == heaters.begin())
ret = max(ret, *lb - h);
else if(lb == heaters.end())
ret = max(ret, h - heaters.back());
else
ret = max(ret, min(*lb - h, h - *(lb - 1)));
*/
}
return ret;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.