Suppose, we have an array of numbers $x_j$ and their corresponding weights $w_j$ where $\sum_j w_j \gt 1$. Now we need to find $x_m$ such that
$$\sum_{j=1}^{m-1} w_j \lt 1/2 \quad \text{and} \quad \sum_{j=m+1}^{n} w_j \ge 1/2$$
Moreover, $x_m > x_j$, $x_m < x_k$ where $j \ne k$. i.e. a solution should be like this --
$$\underbrace{x_1, x_2, \ldots, x_{m-1}}_{\lt \, x_m}, x_m, \underbrace{x_{m+1}, \ldots, x_{n-1}, x_n}_{\ge \, x_m} \\ \underbrace{w_1, w_2, \ldots, w_{m-1}}_{\lt \, 1/2}, w_m, \underbrace{w_{m+1}, \ldots, w_{n-1}, w_n}_{\ge \, 1/2}$$
Moreover, it was also mentioned that I may use Dynamic Programming that could be bounded by $O(n\lg n)$.
EDIT:
$\{x_j, w_j\}: \quad x_j \text{ is the value and } w_j \text{ is the weight.}$
Example Input: $\{10, 0.4\}, \, \{5, 0.1\}, \, \{6, 0.9\}, \, \{2, 0.3\}, \, \{3, 0.1\}$
Example Output: $\{2, 0.3\}, \, \{3, 0.1\}, \, \underbrace{\{5, 0.1\}}_{x_m}, \, \{6, 0.9\}, \, \{10, 0.4\}$
How I tried
Step 1: First sort the list according to $w_j$. -- $O(n \lg n)$
Step 2: Start from the first element from the left, add the weights $w_j$ until $\sum_j w_j \ge \, 1/2$. The current $x_j$ is the $x_m$. -- $O(n)$
Step 3: Stop, now we have two lists. One is on the left $L=\{x_1, x_2, \ldots, x_{m-1}\}$ and the other is on the right $R = \{x_m, x_{m+1}, \ldots, x_n\}$.
Step 4: Go through the list $L$, if there is any value $x_k > x_m$, move $x_k$ into $R$ at an appropriate position. Do this until all elements in $L$ is smaller than $x_m$. -- $O(n^2)$
Step 5: if $L \ne \emptyset$, $x_m$ is the answer, otherwise $x_1$ is the answer.
The overall complexity will be $O(n \lg n) + O(n) + O(n^2) \approx O(n^2)$. I got confused about the DP stuff at the end of the question, so I was wondering if there is really any way to do it in $O(n \lg n)$ (or better), how do I build the optimal substructure in the case of DP?