# Binary Search & Two pointer (Java)

• The first solution I came up with is for each house, find the two heaters between which the house is located using binary search. We can using `Arrays.binarySearch()` Function. The time complexity for this process is `O(houses*lg(heaters))`

Then I realized that since houses and heaters are all sorted. We can search for the position where the houses located by using two pointers instead of using binary search.

``````i: house index   j: heater index

IF houses[i]<heaters[j]: house i is located between heater j-1( If it exist) and heater j. update max
IF houses[i]==heaters[j]: continue
IF houses[i]>heaters[j]: increase j, we have not find the location
``````

The time complexity for this process is `O(houses+heaters)`

I find it's quite annoying to handle the edge cases in a elegant way.

#### Solution 1:

``````public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int max=0;
for(int i=0;i<houses.length;i++){
int index=Arrays.binarySearch(heaters,houses[i]);
if(index<0){
index=-(index+1);
if(index==0) max=Math.max(max,heaters[0]-houses[i]);
else if(index==heaters.length) max=Math.max(max,houses[i]-heaters[heaters.length-1]);
else max=Math.max(max,Math.min(houses[i]-heaters[index-1], heaters[index]-houses[i]));
}
}
return max;
}
}
``````

#### Solution 2:

``````public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int max=0;
int i=0, j=0;
while(i<houses.length){
if(j==heaters.length) {
max=Math.max(max,houses[i]-heaters[j-1]);
i++;
continue;
}
if(houses[i]<=heaters[j]){
max=Math.max(max,Math.min(j-1>=0?houses[i]-heaters[j-1]:Integer.MAX_VALUE, heaters[j]-houses[i]));
i++;
}else j++;
}
return max;
}
}
``````

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