# Leetcode 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

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

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

- We can utilize binary search to find the index s which makes both s and s + k have almost the same difference to x. In each iteration, if mid + k is closer to x, it means elements from mid + 1 to mid + k are all equal or closer to x due to ascending order. Thus we can discard mid by assigning left to mid + 1. Otherwise, it means mid is equal or closer to x than mid + k so we remain mid in next comparison. In the end, we will found an index s that has the balanced range with s + k.
- neetcode gözden geçir.

```
class Solution:
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
# approach: use binary search to find the start which is closest to x
left = 0
right = len(arr) - k
while left < right:
mid = left + (right - left) // 2
# mid + k is closer to x, discard mid by assigning left = mid + 1
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
# mid is equal or closer to x than mid + k, remains mid as candidate
else:
right = mid
# left == right, which makes both left and left + k have same diff with x
return arr[left : left + k]
```