658. 找到 K 个最接近的元素

Approach 1，二分+双指针

1. 假设x插入arr数组中，通过二分找到x在有序数组中应该放置的位置
2. 从该位置起，设定双指针，往两头走
3. 双指针指向的两个值中，每次选出一个与x差值更小加入到结果集中，同时指针移动一位
4. 结果集添加k个数结束循环

难点

1. 快速写出二分定位插入位置

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        int n = arr.length;
        int l = 0, r = n-1;
        while (l < r) {
            int mid = l + ((r-l) >> 1);
            if (arr[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        
        l = r - 1;
        
        int max = Integer.MAX_VALUE;
        while (k > 0 && (l >= 0 || r <= n-1)) {
            int dl = max;
            int dr = max;
            if (l >= 0) {
                dl = Math.abs(arr[l] - x);
            }
            if (r <= n-1) {
                dr = Math.abs(arr[r] - x);
            }

            if (dl <= dr) {
                res.add(arr[l]);
                l--;
            } else {
                res.add(arr[r]);
                r++;
            }

            k--;
        }
        Collections.sort(res);
        return res;
    }
}