My Java Binary Search Solution, Concise and Easy to Understand


  • 1
    S
    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            int m = houses.length;
            int n = heaters.length;
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int left = 0;
            int right = Math.max(Math.abs(houses[0] - heaters[n - 1]), Math.abs(houses[m - 1] - heaters[0]));
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (cover(mid, houses, heaters)) right = mid - 1;
                else left = mid + 1;
            }
            return left;
        }
        
        public boolean cover(int radius, int[] houses, int[] heaters) {
            int m = houses.length;
            int n = heaters.length;
            int j = 0;
            for (int i = 0; i < n; i++) {
                long low = heaters[i] - radius;
                long high = heaters[i] + radius;
                while (j < m && low <= (long)houses[j] && (long)houses[j] <= high) j++;
            }
            return j == m;
        }
    }
    

Log in to reply
 

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