LeetCode 1300. 转变数组后最接近目标值的数组和（二分查找）

示例 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

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
    	int i, l, r, mid, idx, diff, mindiff = INT_MAX, n = arr.size(), ans=INT_MAX;
    	sort(arr.begin(),arr.end());
    	vector<int> presum(arr);
    	for(i = 1; i < n; ++i)
    		presum[i] += presum[i-1];//前缀和
    	l = 0, r = arr[n-1];//范围
    	while(l <= r)
    	{
    		mid = l+((r-l)>>1);
    		idx = binsearch(arr, mid);//二分查找mid这个值在数组中的位置
    		diff = (idx>0? presum[idx-1] : 0) +(n-idx)*mid-target;
    		//函数式的值，函数单调递增
    		if(abs(diff) < mindiff)
    		{
    			mindiff = abs(diff);
    			ans = mid;//有更小的
    		}
            else if((abs(diff) == mindiff))
                ans = min(ans,mid);//相等的情况下取更小的
    		if(diff < 0)//小了，要让他增大，在0左右寻找
    			l = mid+1;
    		else if(diff > 0)
    			r = mid-1;
            else
                return ans;
    	}
    	return ans;
    }

	int binsearch(vector<int>& arr, int val)
	{	//找第一个大于val的数的下标
		int l = 0, r = arr.size()-1, mid;
		while(l <= r)
		{
			mid = l+((r-l)>>1);
			if(arr[mid] > val)
			{
				if(mid==0 || arr[mid-1] <= val)
					return mid;
				else
					r = mid-1;
			}
			else
				l = mid+1;
		}
		return arr.size();//没找到，全部小于val
	}
};