Claim 1: Optimal choice for $$$x$$$, given some $$$m$$$ values, will then surely be between the $$$m$$$ , i.e. $$$p_{1} \le x \le p_{m}$$$.

Proof: (By contradiction) Let's assume that $$$x \lt p_{1}$$$, Then obviously $$$x = p_{1}$$$ is better option. Similiarly for other case, if $$$x \gt p_{m}$$$, then $$$x = p_{m}$$$ is better. So Claim 1 must be true.

Claim 2: When you take any $$$x$$$ such that, $$$p_{1} \le x \le p_{m}$$$, then Farthest point from $$$x$$$ is either $$$p_{1}$$$ or $$$p_{m}$$$.

Proof: This is obvious, because we have $$$p_{1}$$$ through $$$p_{m}$$$ in sorted manner.

Final Claim: Best option for x ( as a real number ) is $$$(p_{1} + p_{m})/2$$$. So, if we require integer point for $$$x$$$, we must check floor and ceil of this real number.

Proof: Since we want such $$$x$$$, that farthest point among $$$m$$$ points is closest to $$$x$$$, and we know that farthest point among $$$m$$$ points is either first one, or last one ( by Claim 2 ), then to minimize the distance from farthest point we must have distance of $$$x$$$ from both $$$p_{1}$$$ and $$$p_{m}$$$ to be least possible, which means $$$x$$$ must be roughly at mid-point of $$$p_{1}$$$ and $$$p_{m}$$$.

Solve these parts with $$$m = k+1$$$.