A problem solved by weighted median
I don't see how using the select algorithm, or indeed any algorithm, is useful here. Instead, try to use the following observation:


  Let $I = \{ i : x_i &lt; x_p \}$ and $J = \{ j : x_j &gt; x_p \}$. Then the derivative of your objective function with respect to $x_p$ is $$\sum_{i \in I} w_i - \sum_{j \in J} w_j. $$