640. The k Values Nearest a Target
A non-decreasing list is given, along with k and a target x. Choose the k values closest
to x, where closeness is |value - x|. When two values are equally close, the SMALLER one is
preferred.
Print the chosen values in non-decreasing order.
1 2 3 4 5, k = 4, x = 3 -> 1 2 3 4
1 2 3 4 5, k = 4, x = -1 -> 1 2 3 4
1 1 1 10 10 10, k = 1, x = 9 -> 10
## The answer is always a contiguous block
This is the observation the whole solution rests on. The k closest values to x form a
CONSECUTIVE run of the sorted list.
Why: suppose the chosen set skipped some value v while including something beyond it on the
same side. Then v is at least as close to x as that outer value, so swapping it in is no
worse, and repeating the swap closes every gap.
So the job is not to pick k values; it is to pick WHERE the window of size k starts.
## Shrink from both ends
Start with the whole list and discard from whichever end is further from x, until exactly
k remain:
lo = 0, hi = n-1
while hi - lo + 1 > k:
if |a[lo] - x| > |a[hi] - x|: lo += 1
else: hi -= 1
Each round throws away one value that is at least as far as everything remaining on the other side, so nothing closer is ever discarded.
## Where the tie-break lives
The else branch handles both "the right end is further" and "the two ends are equally far".
On a tie it discards the RIGHT end, which keeps the smaller value, exactly as the statement
requires.
Writing the condition as >= instead would discard the left end on a tie and prefer the larger
value. That single character is the entire tie-break, and 1 2 3 4 5 with x = 3 and k = 4
is the test: the answer is 1 2 3 4, not 2 3 4 5.
## A target outside the list
If x is below everything, the answer is the first k values; if above, the last k. The
loop gets both without a special case, because one end is always clearly further.
## Cost
Time O(n - k). Space O(1) beyond the output.
A binary search for the window start makes it O(log n + k), which matters only when k is
tiny against n.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-10^9 ≤ each value and x ≤ 10^9` - the list is non-decreasing
Input
The first line contains three integers n, k and x.
The second line contains n integers in non-decreasing order.
Output
Print the k chosen values in non-decreasing order on one line, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.