658 Find K Closest Elements

Given a sorted array, two integerskandx, find thekclosest elements toxin the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input:
 [1,2,3,4,5], k=4, x=3

Output:
 [1,2,3,4]

Example 2:

Input:
 [1,2,3,4,5], k=4, x=-1

Output:
 [1,2,3,4]

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10 4
3. Absolute value of elements in the array and x will not exceed 10 4

UPDATE (2017/9/19):
Thearrparameter had been changed to anarray of integers(instead of a list of integers).Please reload the code definition to get the latest changes.

Solution)

class Solution {
    public int searchIndex(int[] arr, int x) {
        if (arr.length > 0 && arr[0] > x) return 0;
        if (arr.length > 0 && arr[arr.length-1] < x) return arr.length-1;
        int left=0,right=arr.length-1;
        while(left<right) {
            int mid = (left+right)/2;
            if (arr[mid]==x) return mid;
            if (arr[mid]<x) left=mid+1;
            else right=mid-1;
        }

        return arr[left]-x >= x-arr[right] ? right : left;
    }
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        int idx = searchIndex(arr,x);
        list.add(arr[idx]);
        int count=1;
        int left=idx-1,right=idx+1;
        while(count<k) {
            if (left >= 0 && right < arr.length) {
                if (x-arr[left] <= arr[right]-x) {
                    list.add(0,arr[left--]);
                } else {
                    list.add(arr[right++]);
                }
                count++;
            } else if (left < 0 && right < arr.length) {
                while(count<k) {
                    list.add(arr[right++]);
                    count++;
                }
            } else if (left >=0 && right == arr.length) {
                while(count<k) {
                    list.add(0,arr[left--]);
                    count++;
                }                
            }
        }
        return list;
    }
}

Solution 2) By using StefanPochmann Binary Search, we can find the start and end index for the result by searching.

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int start = 0, end = arr.length-k;

        while(start<end) {
            int mid = (start + end)/2;
            if (x - arr[mid] > arr[mid+k]-x)
                start = mid + 1;
            else
                end = mid;
        }

        List<Integer> results = new ArrayList<Integer>();
        for(int i=start;i<start+k;i++){
            results.add(arr[i]);
        }
        return results;    
    }
}