Leetcode 1300: Sum of Mutated Array Closest to Target

https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/description/

Notes:

This question is designed for binary search. Why?

Let say the answer is in a range of [left, right], then we can choose mid = left + (right - left) / 2.

Then we can compare val = mid and  val = mid - 1. If mid gives a better (or closer to target) than mid - 1, then we can say that the answer should be in the range of [mid, right];

otherwise, it should be in the range of [left, mid-1].

One sentence summary: binary search for a "u" shape sorted array.

See the code below:

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        long a = -1e9, b = 1e9;
        return help(arr, a, b, target);
    }

private:
    int cal(int a, vector<int>& arr, int tar) {
        long sum = 0;
        for(auto &c : arr) {
            if(c<=a) sum += c;
            else sum += a;
        }
        return abs(sum - tar);
    }

    int help(vector<int>& arr, long left, long right, int tar) {
        if(left == right) return left; //base case
        if(left + 1 == right) {//base case due to boundary
            return cal(left, arr, tar) <= cal(right, arr, tar) ? left : right;
        }
        long mid = left + (right - left)/2;
        long x = cal(mid, arr, tar), y = cal(mid-1, arr, tar);
        if(y<=x) return help(arr, left, mid, tar);
        return help(arr, mid, right, tar);
    }
};