# 658. Find K Closest Elements

## Description

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

## Solutions

Solution 1: Sort

Solution 2: Binary search

• class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = 0;
int right = arr.length - k;
while (left < right) {
int mid = (left + right) >> 1;
if (x - arr[mid] <= arr[mid + k] - x) {
right = mid;
} else {
left = mid + 1;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = left; i < left + k; ++i) {
}
return ans;
}
}

• class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - k;
while (left < right) {
int mid = (left + right) >> 1;
if (x - arr[mid] <= arr[mid + k] - x)
right = mid;
else
left = mid + 1;
}
return vector<int>(arr.begin() + left, arr.begin() + left + k);
}
};

• class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
left, right = 0, len(arr) - k
while left < right:
mid = (left + right) >> 1
if x - arr[mid] <= arr[mid + k] - x:
right = mid
else:
left = mid + 1
return arr[left : left + k]


• func findClosestElements(arr []int, k int, x int) []int {
left, right := 0, len(arr)-k
for left < right {
mid := (left + right) >> 1
if x-arr[mid] <= arr[mid+k]-x {
right = mid
} else {
left = mid + 1
}
}
return arr[left : left+k]
}

• function findClosestElements(arr: number[], k: number, x: number): number[] {
let left = 0;
let right = arr.length - k;
while (left < right) {
const mid = (left + right) >> 1;
if (x - arr[mid] <= arr[mid + k] - x) {
right = mid;
} else {
left = mid + 1;
}
}
return arr.slice(left, left + k);
}


• impl Solution {
pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
let k = k as usize;
let n = arr.len();
let mut left = 0;
let mut right = n - k;
while left < right {
let mid = left + (right - left) / 2;
if x - arr[mid] > arr[mid + k] - x {
left = mid + 1;
} else {
right = mid;
}
}
arr[left..left + k].to_vec()
}
}