## 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 10^4
3. Absolute value of elements in the array and x will not exceed 10^4

Thoughts:

1. Binary -searching the first index i that arr[i] is closer or equally close to arr[i+k] (Original Post)
2. Binary-searching for`x`and then expanding to the left and to the right: The idea is to find the first number which is equal to or greater than`x`in`arr`. Then, we determine the indices of the start and the end of a subarray in`arr`, where the subarray is our result. The time complexity is `O(logn + k)` .

Code: Binary -searching for the first index i T: O(log(n-k))

``````class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int i = 0, j = arr.length - k;
while (i < j){
int mid = (i & j) + ((i ^ j) >> 1);
// int mid = i + (j - i >> 1);
if(x - arr[mid] > arr[mid + k] - x)
i = mid + 1;
else
j = mid;
}
List<Integer> res = new ArrayList<>();
for (int b = i; b < i + k; ++b) res.add(arr[b]);
return res;
// return Arrays.stream(Arrays.copyOfRange(arr, i, i + k)).boxed().collect(Collectors.toList());

}
}
``````

Python: T: O(log(n-k))

``````class Solution(object):
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
i, j = 0, len(arr) - k
while i < j:
mid = (i & j) + ((i^j)>> 1)
if x - arr[mid] > arr[mid + k] - x: # arr is sorted
i = mid + 1
else:
j = mid

return arr[i:i+k]
``````

Code 2: Reference T: O(log(n)+k)

``````  public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int index = Collections.binarySearch(arr, x);
if(index < 0) index = -(index + 1);
int i = index - 1, j = index;
while(k-- > 0){
if(i < 0 || (j < arr.size() && Math.abs(arr.get(i) - x) > Math.abs(arr.get(j) - x)))j++;
else i--;
}
return arr.subList(i+1, j);
}
``````