1300. 转变数组后最接近目标值的数组和
给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。
如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
请注意，答案不一定是 arr 中的数字。
示例：
输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361
分析：
（1）题目说-会将数组中所有大于value的值变成value，提示可以将数组arr进行排序。这样就方便我们统计那些数组元素保留原值，其他元素变为value。这样得到一个公式arr[i] * times + res（times，大于value的元素个数，res，小于value的元素的值）。就可以拿这个值来与target比较。
（2）上一步得到了比较的公式。进一步思考如何比较。如果不断+1遍历，对于示例二来说就非常的慢。因此可以用二分法来进行搜索。
（3）二分搜索区间：
对于数组元素 (arr[i])，如果(arr[i] * times + res > target)而(arr[i - 1] * times + res < target)。就可以判断我们需要的答案就在([arr[i], arr[i - 1]])中。
再对特殊情况考虑，对于第一个元素，搜索区间为([0, arr[0]])。
代码（Python）：
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
def binary_search(left: int, right: int) -> int:
"""
二分法，获得left，right中乘以times的积的差值最接近target的值
"""
while left <= right:
mid = (left + right) // 2
mid_val = mid * times + res
if mid_val == target:
return mid
if mid_val < target:
left = mid + 1
if mid_val > target:
right = mid - 1
if abs(left * times + res - target) < abs(right * times + res - target):
return left
else:
return right
ans = 0
arr.sort()
if sum(arr) <= target:
return arr[-1]
n = len(arr)
i = 0
times = n
res = 0
# 当arr[i] * n > target and arr[i - 1] * n < target
# 设置查找区间(arr[i - 1], arr[i])
while arr[i] * times + res < target:
res += arr[i]
i += 1
times -= 1
if arr[i] * times + res == target:
return arr[i]
if arr[i] * times + res > target:
if i == 0:
ans = binary_search(0, arr[0])
else:
ans = binary_search(arr[i - 1], arr[i])
return ans