# Short and Clean Java Binary Search Solution

• 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.

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

for (int house : houses) {
int index = Arrays.binarySearch(heaters, house);
if (index < 0) {
index = -(index + 1);
}
int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;
int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;

result = Math.max(result, Math.min(dist1, dist2));
}

return result;
}
}
``````

• Just a small variation (we can ignore houses on heaters, and I like `~`):

``````public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int result = 0;

for (int house : houses) {
int index = Arrays.binarySearch(heaters, house);
if (index < 0) {
index = ~index;
int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;
int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;

result = Math.max(result, Math.min(dist1, dist2));
}
}

return result;
}``````

• @StefanPochmann You are totally correct! I will keep my original post and let other people figure out why your post is smarter :D

• This post is deleted!

• ``````if (index < 0) {
index = ~index;
}
``````

Just wonder if the above code is executed when the position of a house is less than the position of the first heater, which causes Arrays.binarySearch to return -1?

Thanks!

• @jun711 Yes. According to Java doc : https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[], int)

Returns:
index of the search key, if it is contained in the array; otherwise, `(-(insertion point) - 1)`. The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

• @shawngao Thank you. Never noticed this.

• @shawngao Thanks! That's how I got -1 too.

• Nice explanation. Here's the same thing in python

``````    def findRadius(self, houses, heaters):
def binsearch(nums, target) :
i = 0; j = len(nums)
while i < j :
mid = i + (j-i) / 2
if nums[mid] < target : i = mid + 1
else : j = mid
return i

heaters.sort()

result = -sys.maxint - 1

for house in houses :
index = binsearch(heaters, house)
leftHeaterDistance = house - heaters[index - 1] if index > 0 else sys.maxint
rightHeaterDistance = heaters[index] - house if index < len(heaters) else sys.maxint
result = max(result , min(leftHeaterDistance, rightHeaterDistance))

return result
``````

• @StefanPochmann Does it mean that if (index >= 0), you don't need to update result in this interation?

• Brilliant!!! Espcially the use of '~'.
Learn a lot, thanks!

• @shawngao isn't this (n + m)logn? If n > m, it is worse than sorting both and then merge.

• Let TreeSet do the sorting, and indexing.

`````` public int findRadius(int[] houses, int[] heaters) {
TreeSet<Integer> set = new TreeSet<>();
for (int heater : heaters)

int index = 0, res = 0;
for (int house : houses) {
int dist1 = set.ceiling(house) == null ? Integer.MAX_VALUE : set.ceiling(house) - house;
int dist2 = set.floor(house) == null ? Integer.MAX_VALUE : house - set.floor(house);
res = Math.max(res, Math.min(dist1, dist2));
}

return res;
}``````

• @shawngao isn't this (n + m)logn? If n > m, it is worse than sorting both and then merge.

The top post says it's `max(O(nlogn), O(mlogn))`, which looks correct.
(n + m)logn<= 2*Math.max(m, n)*logn

• @zzhai yes, i guess i wanted to say i prefer (n + m)*logn, e.g. if we know n > m, the the other way becomes nlogn irrelevant of m, (n+m)*logn is more accurate. Of course both ways are correct.

• Guys, I am little confused why we are selecting the MIN distance between the house and the heater?

• @StefanPochmann Hello! I get what `~` does here. But I am not familiar with bit operations. Could you explain a little bit?

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