# 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:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 10^4
Absolute value of elements in the array and x will not exceed 10^4

# Solution

Approach 1: sort array in place by distance to x, then take the first k items. O(NlogN) time.

Approach 2: binary search for x's insertion point (the index), then use two points to point to both sides of the index. O(logN + k) time.

# Code (Python)

Approach 2:

import bisect
import collections

class Solution:
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        insert_index = bisect.bisect_left(arr, x)
        result = collections.deque()
        left, right = insert_index - 1, insert_index
        while len(result) < k:
            if left < 0:
                result.append(arr[right])
                right += 1
            elif right >= len(arr):
                result.appendleft(arr[left])
                left -= 1
            else:
                if x - arr[left] <= arr[right] - x:
                    result.appendleft(arr[left])
                    left -= 1
                else:
                    result.append(arr[right])
                    right += 1
        return list(result)

# Code (C++)

Approach 1:

Approach 2: