In class, we learned a linear time algorithm that finds the median of an array of numbers. We now wish to solve a more general problem using this algorithm. The input is an (unsorted) array of numbers x_1, x_2, ..., x_n, each with an associated positive weight (we denote the weight of X_i by w_i) such that the sum of weights is 1 (i.e., sigma_i = 1^n w_i = 1). Suppose phi defines an ordering of indices such that x_phi(1), x_phi(2), , x_phi(n) is sorted. The weighted median of the numbers is the value X_phi(m) such that sigma_i = 1^m - 1w_phi(i)