## 658. Find K Closest Elements

Given a sorted array, two integers `k` and `x`, find the `k` closest elements to `x` in 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 104
3. Absolute value of elements in the array and x will not exceed 104

UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Using Collection.sort( ) [Accepted]

\n

Algorithm

\n

Intuitively, we can sort the elements in list `arr` by their absolute difference values to the target `x`. Then the sublist of the first k elements is the result after sorting the elements by the natural order.

\n\n

Note: This solution is inspired by @compton_scatter.

\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Collections.sort() uses binary sort so it has a complexity.

\n
• \n
• \n

Space complexity : . The in-place sorting does not consume any extra space. However, generating a k length sublist will take some space.

\n
• \n
\n
\n

#### Approach #2 Using Binary Search and Two Pointers [Accepted]

\n

Algorithm

\n

The original array has been sorted so we can take this advantage by the following steps.\n1. If the target `x` is less or equal than the first element in the sorted array, the first `k` elements are the result.\n2. Similarly, if the target `x` is more or equal than the last element in the sorted array, the last `k` elements are the result.\n3. Otherwise, we can use binary search to find the `index` of the element, which is equal (when this list has `x`) or a little bit larger than `x` (when this list does not have it). Then set `low` to its left `k-1` position, and `high` to the right `k-1` position of this `index` as a start. The desired k numbers must in this rang [index-k-1, index+k-1]. So we can shrink this range to get the result using the following rules.\n * If `low` reaches the lowest index `0` or the `low` element is closer to `x` than the `high` element, decrease the `high` index.\n * If `high` reaches to the highest index `arr.size()-1` or it is nearer to `x` than the `low` element, increase the `low` index.\n * The looping ends when there are exactly k elements in [low, high], the subList of which is the result.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . is for the time of binary search, while is for shrinking the index range to k elements.

\n
• \n
• \n

Space complexity : . It is to generate the required sublist.

\n
• \n
\n

Analysis written by: @Mr.Bin

\n
'