# 658 Find K Closest Elements

Given a sorted integer array `arr`, two integers `k` and `x`, return the `k` closest integers to `x` in the array. The result should also be sorted in ascending order.

An integer `a` is closer to `x` than an integer `b` if:

• `|a - x| < |b - x|`, or
• `|a - x| == |b - x|` and `a < b`

Example 1:

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

Example 2:

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

Constraints:

• `1 <= k <= arr.length`
• `1 <= arr.length <= 104`
• `arr` is sorted in ascending order.
• `-104 <= arr[i], x <= 104`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 `````` ``````import bisect class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: i = bisect.bisect_left(arr, x) l, r = i - 1, i while r - l <= k: if l == -1: r += 1 elif r == len(arr) or abs(arr[l] - x) <= abs(arr[r] - x): l -= 1 else: r += 1 return arr[l+1:r] ''' Binary search for the left boundary ''' class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: ''' If the element at arr[mid] is closer to x than arr[mid + k], then that means arr[mid + k], as well as every element to the right of it can never be in the answer. This means we should move our right pointer to avoid considering them. The logic is the same vice-versa - if arr[mid + k] is closer to x, then move the left pointer. ''' # Initialize binary search bounds left = 0 right = len(arr) - k # Binary search against the criteria described while left < right: mid = (left + right) // 2 if x - arr[mid] > arr[mid + k] - x: left = mid + 1 else: right = mid return arr[left:left + k]``````