Minimizing $L_2$ norm of a vector with two distinct entries Let $d\in\mathbb N$ and denote $V=\bigcup_{a,b\in\mathbb R}\{a,b\}^d$, the set of all vectors with two distinct values.
Given a vector $x\in \mathbb R^d$, I want to compute some $v^*\in V$ such that $\left\lVert x-v^*\right\rVert_2\le \left\lVert x-v\right\rVert_2$ for any $v\in V$.

What would be the fastest algorithm to compute $v^*$?


It seems possible to show that the problem is equivalent to finding a threshold $T\in\mathbb R$ such that $v^*_i=\begin{cases}a &amp; \mbox{if $x_i&lt;T$}\\b &amp; \mbox{otherwise}\end{cases}$, where $a$ is the mean of all entries smaller than $T$ and $b$ is the mean of all entries larger than or equal to $T$.
This suggests a $O(d^2)$ time algorithm. Can we find the optimal $T$ faster?

I am also interested in an extension of the problem where we look at $V_4=\bigcup_{a,b,c,z\in\mathbb R}\{a,b,c,z\}^d$ instead of $V$. How fast can we find $v^*$ in this setting?
(This is probably a comment but I cannot comment)
This seems to be 1-dimensional $k$-means clustering for $k=2$ and $k=4$. Here is a reference that gives a $O(kn + n \log n)$ algorithm for 1-d $k$-means clustering: Grønlund, Larsen, Mathiasen, Nielsen, Schneider, Song, Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. It seems similar to the algorithm given in the comments.