刚写完 二分总结 ，LeetCode每日一题就正好是一道二分题，趁热打铁把题解写了。对于二分模板还不太熟悉的同学可以先去看看总结，回顾一下。

题目描述

给你一个整数数组arr 和一个目标值target ，请你返回一个整数value，使得将数组中所有大于value 的值变成value 后，数组的和最接近target（最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近target的方案，请你返回这些整数中的最小值。

请注意，答案不一定是arr 中的数字。

示例 1：

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

示例 2：

输入：arr = [2,3,5], target = 10
输出：5

示例 3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

提示：

• $1 <= arr.length <= 10^4$
• $1 <= arr[i], target <= 10^5$

算法思路

该题要求找到一个整数val，然后将数组中所有大于val的值都变为val,使得改变后的数组和与target的绝对值最小，同时val也应该最小。

通过题意，我们直到如果val的选择比数组中的任何一个数都大，那么数组中不会有数会被改变，由于我们需要找到最小的val,那么大于数组中最大值的val的取值就没有意义，因此我们就找到了val的上边界。同时由于target和数组中的数的取值均为正数，那么如果val为负数的话，数组中的所有数也会变成负数，此时数组和也为负数。此时数组和与target的绝对值必然大于targrt与0的值，因此我们的val的下边界可以取为0.

由于我们需要找到使得改变后的数组和与taeget差绝对值的最小值，最理想的情况就是能够找到一个val，使改变后的数组和刚好等于target,但是也可能不那么幸运，并不能找到一个val使数组和与target相同。那么能够使绝对值最小的数组和要么是大于taeget,要么是小于target,因此我们的二分思路就来了。找到能够满足数组和大于等于target的最小的val,此时数组和与target的差为正数。但是由于我们需要找到最小的val,因此我们还需要再比较val与val - 1时，哪个值能够使得绝对值最小。

具体步骤：

• val的下边界为0，上边界为数组中最大值
• 二分val的值，找到使得数组和大于等于target的最小val值
• 返回val与val - 1中使得数组和与target差较小的那个

C ++代码

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        int l = 0, r = arr[0];
        for (int i = 1; i < arr.size(); i ++) r = max(r, arr[i]); //找到右边界
        while (l < r)
        {
            int mid = l + r >> 1;
            if (cal(mid, arr) >= target) r = mid; //二分找到大于等于target的最小数组和
            else l = mid + 1;
        }

        if (abs(cal(l - 1, arr) - target) <= abs(cal(l, arr) - target)) //如果小于target时绝对值更小
            return l - 1;
        return l;
    }

    int cal(int val, vector<int>& arr) //计算val改变后的数组和
    {
        int sum = 0;
        for (auto x : arr) sum += min(x, val);
        return sum;
    }
};