Find K Closest Elements

From the sorted integer array arr, pick the k values nearest to x.

If |a - x| == |b - x|, the smaller number is chosen. The result should be sorted in ascending order.

Example:

• Input: arr = [1,2,3,4,5], k = 4, x = 3
• Output: [1,2,3,4]

The heap baseline — O(n log k). Treat it like any top-k problem: push every value onto a max-heap keyed by (|value − x|, value) and pop whenever it holds more than k. It works on any array, sorted or not.

A sorted array does better — O(n). Distance from x only falls and then rises along a sorted array, so the k closest values are one contiguous run, and the farther end of any window is its farthest value. Start with the whole array as the window [L, R] and shrink it:

1. While the window holds more than k values, compare its two ends.
2. If arr[L] is strictly farther from x than arr[R], drop L.
3. Otherwise drop R — on a tie the smaller value, arr[L], is the one to keep.
4. Return arr[L..R].

Binary search can find where the window starts in O(log(n − k)); the shrink is the simplest correct version, and it is what the code below does.

The window [L, R] starts as the whole array, with each value's distance from x beneath it. Its two ends are compared and the farther one is dropped until k values remain.