Modify protocol Halving as follows: In iteration i,

(a) discard from both Dix and Diy

, all elements greater than max{mi x,mi y

} and all those smaller than min{mi x,mi y

}, where Dix and Diy denote the set of elements of Dx and Dy still under consideration at the beginning of stage i, and mi x and mi y denote their lower medians;

(b) transform the problem again into a median finding one.

Write the corresponding algorithm, GeneralHalving, prove its correctness, and analyze its complexity.