Find K Closest Elements

https://shuati.gitbook.io/crack-lintcode/~/edit/drafts/-LMG97oDZL7Yvkxmwrgu/binary-search/find-k-closest-elements

leetcode 版本，要求返回的 顺序，并且返回list,中规中矩，时间复杂度O(longn +k)

注意：在二分里，当arr[mid] == x时，让start 右移和让end 左移，都没区别，在确定index时，如果没有x的话，就找离x最近 比他小的第一个数，所以要检查end 和start的值是不是小于等于x

在给左右pointer赋值时，把index付给左是因为，同等条件下倾向于加左边，直接把index付给左边，第一次就会把index这个值加进去，另外注意往list里插入的顺序

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        
        List<Integer> list = new ArrayList<>();
        
        if(arr == null || arr.length == 0)
            return list;
        
        int start = 0, end = arr.length - 1;
        
        while(start + 1 < end){
            int mid = start + (end - start)/2;
            
            if(arr[mid] >= x)
                end = mid;
            
            else
                start = mid;
        }
        
        int index = arr[end] <= x ? end : arr[start] <= x ? start : -1;
        
        int left = index, right = index + 1;
        
        for(int i = 0; i < k; i++){
            if(leftCloser(left,right,x,arr)){
                list.add(0,arr[left]);
                left--;
            }else{
                list.add(arr[right]);
                right++;
            }
        }
        
        return list;
        
        
        
    }
    
    public boolean leftCloser(int left, int right, int target, int[] arr){
        if(left < 0){
            return false;
        }
        
        if(right >= arr.length)
            return true;
        
        return target - arr[left] <= arr[right] - target;
    }
}