Find K Closest Elements
Medium · binary search
You are given a list arr of integers sorted in ascending order (duplicates are allowed), a count k and a target value x. The value x does not have to appear in arr.
A value a is closer to x than a value b if |a - x| < |b - x|. If the two distances are equal, the smaller value counts as closer.
Return the k values of arr that are closest to x, sorted in ascending order. If a value appears several times in arr, each copy is a separate candidate.
Examples
Example 1
Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]
The distances are 2, 1, 0, 1, 2. The 1 and the 5 are equally far, and the smaller one, 1, wins the last place.
Example 2
Input: arr = [1, 2, 3, 4, 5], k = 2, x = 10
Output: [4, 5]
10 is beyond the end of the list, so the two largest values are closest.
Example 3
Input: arr = [2, 4, 6, 8], k = 2, x = 5
Output: [4, 6]
Constraints
- 1 <= k <= len(arr) <= 10^4
- -10^4 <= arr[i], x <= 10^4
- arr is sorted in ascending order.