1
/**
2
 * @param {number[]} arr
3
 * @param {number} target
4
 * @return {number}
5
 */
6
var findBestValue = function (arr, target) {
7
  const sortedArr = [...arr].sort(function (a, b) {
8
    return a - b;
9
  });
10
  var lowestValue = Math.min(
11
    sortedArr[arr.length - 1],
12
    Math.floor(target / arr.length)
13
  );
14
  var higestValue = Math.min(sortedArr[arr.length - 1], target);
15
  var value, deltaLeft, deltaRight;
16

17
  while (true) {
18
    candidateRight = Math.ceil((lowestValue + higestValue) / 2);
19
    candidateLeft = candidateRight - 1;
20
    deltaLeft = calculateDeltaForCandidate(sortedArr, target, candidateLeft);
21
    if (deltaLeft == 0) {
22
      return candidateLeft;
23
    }
24
    deltaRight = calculateDeltaForCandidate(sortedArr, target, candidateRight);
25
    if (deltaRight == 0) {
26
      return candidateRight;
27
    }
28
    if (deltaRight == 0) {
29
      return candidateRight;
30
    }
31
    if (candidateRight == higestValue) {
32
      return deltaLeft <= deltaRight ? candidateLeft : candidateRight;
33
    }
34
    if (deltaLeft <= deltaRight) {
35
      higestValue = candidateLeft;
36
    } else {
37
      lowestValue = candidateRight;
38
    }
39
  }
40
};
41

42
var calculateDeltaForCandidate = function (sArr, target, candidate) {
43
  var sum;
44
  //find idx lover then candidate
45
  for (var i = 0; i < sArr.length; i++) {
46
    if (sArr[i] >= candidate) {
47
      sum =
48
        sArr.slice(0, i).reduce((partialSum, a) => partialSum + a, 0) +
49
        (sArr.length - i) * candidate;
50
      return Math.abs(sum - target);
51
    }
52
  }
53
  return NaN;
54
};