We are given a set S of n elements so that the i-th element has value x; and weight wi. All weights are positive real numbers and the sum of all weights is 1, 1 Wi = 1. Let a Wi denote the total weight of all elements in S with values less than a. Let >a 2 a Wi denote the total weight of all elements in S with values greater than a. The weighted median of S is the element x satisfying