Short and Clean Java Binary Search Solution


  • 68

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

  • 38

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

  • 9

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


  • -1
    R
    This post is deleted!

  • 0
    J
    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!


  • 0

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


  • 0
    C

    @shawngao Thank you. Never noticed this.


  • 0
    J

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


  • 5
    L

    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
    

  • 0

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


  • 0
    W

    @StefanPochmann said in Short and Clean Java Binary Search Solution:

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


  • 0
    I

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


  • 3

    Let TreeSet do the sorting, and indexing.

     public int findRadius(int[] houses, int[] heaters) {
            TreeSet<Integer> set = new TreeSet<>(); 
            for (int heater : heaters)  
                set.add(heater); 
            
            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; 
        }

  • 1

    @iaming said in Short and Clean Java Binary Search Solution:

    @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


  • 0
    I

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


  • 0
    Y

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


  • 0

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


Log in to reply
 

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