二分查找算法应用总结
给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。请注意，答案不一定是 arr 中的数字。
力扣（LeetCode）第1300题
①．最小值
②．最大值
value 的最大值为数组 arr 中的最大值。因为当value 大于等于 arr 中的最大值时，数组中的元素不发生变化，对数组的和不再有影响
在 value 的取值范围之内，随着 value 的增大，数组的和是单调递增的。因此在一个有序序列中查找某个值，使用二分查找。
①．等于 target 时：当存在数组和等于 target 时，此为理想情况，绝对的最接近；
②．大于 target 时：当所有的取值都使数组和大于 target 时，此时需要找一个最小的值，使更接近target ；
③．大于 target 时：当所有的取值都使数组和小于 target 时，此时需要找一个最大的值，使更接近target ；
综上，可以采用两遍二分查找，分别找出 >=target 和 <=target 时最接近的值，然后取最优结果。
当找到一个 value 时，把 arr分为两部分，前半部分元素值不变，后半部分需要替换成 value ；
①．找分隔点
可以对 arr 排序后，使用二分查找，找到第一个大于 value 的位置；
②．前半部分求和
前半部分元素值不变，可以通过提前构建前缀和，然后直接得到；
②．后半部分求和
后半部分可以根据分隔位置计算出要替换的数量，相乘直接得到。
class Solution {public:int findBestValue(vector<int>& arr, int target) {sort(arr.begin(),arr.end());//先排序,方便查找vector<int> presum(arr.size(),0);//前缀和presum[0] = arr[0];for(int i = 1;i < arr.size();i++){presum[i] = presum[i-1]+arr[i];}int left = 0,right = arr.back();//目标值最小取0，最大取arr中最大值int lowertarget = 0,lowerSum = 0;// <= tager 时，最接近 tager的值 及 和//二分查找while( left <= right ){int mid = left + (right - left ) /2;vector<int>::iterator it = upper_bound(arr.begin(),arr.end(),mid);//第一个大于mid的位置int cursum = 0;//求和if (it == arr.end() ){cursum = presum[arr.size() - 1];}else if (it == arr.begin()){cursum = arr.size()*mid;}else{cursum = presum[it - arr.begin()-1] + (arr.end() - it) *mid;}if( cursum > target ){right = mid-1;}else if( cursum < target )// 找到一个比 target 小的值，缩小范围，优化这个值使更解决 target{lowertarget = mid;lowerSum = cursum;left = mid+1;}else // cursum == target,肯定为最解决，直接返回{lowertarget = mid;lowerSum = cursum;break;}}left = 0, right = arr.back();//初始化左右指针int uppertarget,upperSum = 0;//>=tager 时，最接近 tager的值 及 和while( left <= right ){int mid = left + (right - left ) /2;vector<int>::iterator it = upper_bound(arr.begin(),arr.end(),mid);//第一个大于mid的位置int cursum = 0;//求和if (it == arr.end() ){cursum = presum[arr.size() - 1];}else if (it == arr.begin()){cursum = arr.size()*mid;}else{cursum = presum[it - arr.begin()-1] + (arr.end() - it) *mid;}if( cursum > target ) // 找到一个比 target 大 的值，缩小范围，优化这个值使更解决 target{right = mid-1;uppertarget = mid;upperSum = cursum;}else if( cursum < target ){left = mid+1;}else // cursum == target,肯定为最解决，直接返回{uppertarget = mid;upperSum = cursum;break;}}return abs(lowerSum - target) > abs(upperSum - target) ? uppertarget : lowertarget;}};