1
class Solution {
2
  int max = 0;
3
  int len;
4

5
  public int findBestValue(int[] arr, int target) {
6
    this.len = arr.length;
7

8
    for (int i = 0; i < len; i++) max = Math.max(max, arr[i]);
9

10
    int l = 0;
11
    int r = max;
12
    while (l < r) {
13
      int mid = l + (r - l) / 2;
14

15
      if (check(arr, mid, target) <= check(arr, mid + 1, target)) r = mid;
16
      else l = mid + 1;
17
    }
18
    return l;
19
  }
20

21
  private int check(int[] arr, int value, int target) {
22
    int sum = 0;
23
    for (int e : arr) {
24
      if (e > value) sum += value;
25
      else sum += e;
26
    }
27

28
    return Math.abs(sum - target);
29
  }
30
}