2020-06-14

class Solution {
        public int findBestValue(int[] arr, int target) {
            int[] pre = new int[arr.length];
            Arrays.sort(arr);
            for (int i = 0; i < arr.length; i++) {
                if (i == 0) {
                    pre[i] = arr[i];
                } else {
                    pre[i] = pre[i - 1] + arr[i];
                }
            }
            int l = 0;
            int r = arr[arr.length - 1];
            while (l < r) {
                int mid = (l + r - 1) >> 1;
                int midmid = (r + mid + 1) >> 1;

                int midValue = getValue(arr, pre, mid, target);
                int midmidValue = getValue(arr, pre, midmid, target);
                if (midValue == 0) {
                    return mid;
                }

                if (midmidValue == 0) {
                    return midmid;
                }

                if (midValue > midmidValue) {
                    l = mid + 1;
                } else {
                    r = midmid - 1;
                }
            }
            return l;
        }

        public int getValue(int[] arr, int[] pre, int p, int target) {

            int sum = 0;
            if (arr[0] > p) {
                return Math.abs(arr.length * p - target);
            } else if (arr[arr.length - 1] < p) {
                return Math.abs(pre[pre.length - 1] - target);
            } else {
                int t = binarySearch(arr, p);
                return Math.abs((pre[t] + (arr.length - 1 - t) * p) - target);
            }

        }

        public int binarySearch(int[] arr, int p) {
            int l = 0;
            int r = arr.length - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (arr[mid] > p) {
                    r = mid - 1;
                } else if (arr[mid] < p) {
                    l = mid;
                } else {
                    return mid;
                }
            }
            return l;
        }
}