476. Find K Closest Elements to a Target

Given a sorted integer array arr, an integer k, and an integer x, return the k closest integers to x in sorted order. If two integers are equally close, prefer the smaller one. Solve in O(log(n-k) + k).

Input: A sorted integer array arr, integer k (number to return), and integer x (target).

Output: Sorted array of k closest elements to x.

Examples

Input: [1,2,3,4,5], 4, 3
Output: [1,2,3,4]
Explanation: BS finds best window start. [1,2,3,4] has distances 2,1,0,1 vs [2,3,4,5] has 1,0,1,2. Both same sum — prefer left → [1,2,3,4].

Input: [1,2,3,4,5], 4, -1
Output: [1,2,3,4]
Explanation: Target -1 is left of all; 4 leftmost elements are closest.

Input: [1,2,3,4,5], 4, 10
Output: [2,3,4,5]
Explanation: Target 10 is right of all; 4 rightmost elements are closest.

Constraints

• 1 <= k <= arr.length <= 10^4
• -10^4 <= arr[i], x <= 10^4
• Sorted ascending

Asked by