719 Find K-th Smallest Pair Distance

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;

        int low = 0, high = nums[n - 1] - nums[0];

        while (low < high){
            int mid = low + (high - low) / 2;
            int left = 0, count = 0;
            for (int right = 0; right < n; right++){
                while (nums[right] - nums[left] > mid) left++;
                count += right - left;
            }
            if (count >= k) high = mid;
            else low = mid + 1;
        }

        return low;
    }
}

475 Heaters

class Solution {
    public int findRadius(int[] houses, int[] heaters) {

        Arrays.sort(heaters);

        int ans = 0;
        for (int house : houses){
            int index = Arrays.binarySearch(heaters, house);
            if (index < 0){
                index = -index - 1;
            }

            int dist1 = index - 1 >= 0 ? Math.abs(heaters[index - 1] - house) : Integer.MAX_VALUE;
            int dist2 = index < heaters.length ? Math.abs(heaters[index] - house) : Integer.MAX_VALUE;

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

        return ans;
    }
}

774 Minimize Max Distance to Gas Station

隐藏得深，这种给定范围的就要考虑binary search

class Solution {
    public double minmaxGasDist(int[] stations, int K) {
        double low = 0.0, high = 1e8;
        int n = stations.length;
        while (high - low > 1e-6){
            double mid = low + (high - low) / 2;

            int count = 0;
            for (int i = 0; i < n - 1; i++){
                count += Math.ceil((stations[i + 1] - stations[i]) / mid) - 1;
            }
            if (count > K){
                low = mid;
            }
            else{
                high = mid;
            }
        }

        return high;
    }
}