转变数组后最接近目标值的数组和

/* 
 * Approach: 
 * 1. Sort the array. 
 * 2. Calculate the prefix sum. 
 * 3. Use binary search to find the value which when replacing all elements greater than it minimizes the difference with the target. 
 * Note: Using Java Streams to find the prefix sum and binary search.
 */

import java.util.Arrays;

public class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int n = arr.length;
        int[] prefix = new int[n + 1];
        Arrays.parallelPrefix(arr, (x, y) -> x + y);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        int l = 0, r = arr[n - 1];
        int ans = 0, diff = target;
        while (l <= r) {
            int mid = (l + r) / 2;
            int it = Arrays.binarySearch(arr, mid);
            if (it < 0) it = -it - 1;
            int cur = prefix[it] + (n - it) * mid;
            if (Math.abs(cur - target) < diff) {
                ans = mid;
                diff = Math.abs(cur - target);
            } else if (Math.abs(cur - target) == diff) {
                ans = Math.min(ans, mid);
            }
            if (cur < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}