Given a sorted array, find k elements closest to a target value.
Write a function `k_closest(arr: list[int], k: int, x: int) -> list[int]` that, given a sorted list of integers `arr` and a positive integer `k` (where `k <= len(arr)`), returns a list of the `k` elements from `arr` that are closest to the integer `x`. The result must be in the same relative order as they appear in `arr`. If there is a tie (two elements are equally close), prefer the smaller element, i.e., the one that appears earlier in the array.
Constraints
1 <= k <= len(arr) <= 10^5. The input array is sorted in non-decreasing order, but may contain duplicates. The target x and the array elements are integers within the range [-10^9, 10^9]. The solution should run in O(log n + k) expected time if possible, but any correct O(n) solution is acceptable.
Example
>>> k_closest([1,2,3,4,5], 4, 3)
[1,2,3,4]
>>> k_closest([1,2,3,4,5], 4, -1)
[1,2,3,4]
>>> k_closest([1,1,1,2,3], 3, 1)
[1,1,1]
>>> k_closest([-2,-1,0,1,2,3], 3, 0)
[-1,0,1]
25 points
~25 min