Sum of Mutated Array Closest to Target

给一个数组和一个target, 求一个数字n, 把数组中所有大于n的数字都替换成n以后, 数组的和与target最接近. 这个题是找最接近target的一个数字n, 那么用二叉搜索找即可, 设lo是0, hi是target, 那么mid就是中间假设的答案, 这个答案可以通过题意的改变数组后, 找到和target的差值, 因为我们知道mid是单调递增的, 所以可以用二叉搜索.

class Solution {
    public int findBestValue(int[] arr, int target) {
        int lo = 0;
        int hi = target;
        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int tmp = sum(arr, mid);
            if(tmp == target)
                return mid;
            else if(tmp > target)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        if(Math.abs(sum(arr, lo) - target) >=  Math.abs(sum(arr, lo-1) - target))
            return lo-1;
        else
            return lo;
    }
    
    private int sum(int[] arr, int n) {
        int sum = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] > n) {
                sum += n;
            }
            else {
                sum += arr[i];
            }
        }
        return sum;
    }
}