Leetcode:1300. the sum of the array closest to the target value after transforming the array [dichotomy]

analysis

Given value We can get the current sum
You know , With value An increase in sum Also increased
So with target The distance should be a parabola with the opening upward
In this case , Traverse all possible value value , Just find the first one smaller than the left and right

Ac code

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        n = len(arr)
        arr.sort()
        preSum = list(accumulate(arr))

        # logn
        def get_diff(value):
            idx = bisect_right(arr, value)
            # avoid 0 - 1 = -1
            if idx == 0:
                nowSum = n * value
            else:
                nowSum = preSum[idx - 1] + value * (n - idx)
            #print(preSum[idx - 1], value, n - idx)
            return abs(nowSum - target)
        
        
        minn, maxn = 0, arr[-1]
        for ans in range(minn, maxn + 1):
            #print(ans)
            #print(get_diff(ans - 1), get_diff(ans), get_diff(ans + 1))
            if get_diff(ans - 1) >= get_diff(ans) <= get_diff(ans + 1):
                return ans

summary

function logn Outer layer on
And the previous outer layer on function logn
A little gap