Distributed Median problem - workdog的专栏 - 博客频道 - CSDN.NET

Distributed Median problem - workdog的专栏 - 博客频道 - CSDN.NET

Alice has an array , and Bob has an array . All elements in A and B are distinct. Alice and Bob are interested in finding the median element of their combined arrays. That is, they want to determine which element m satisfies the following property:

This equation says that there are a total of n elements in both A and B that are less than or equal to m. Note that m might be drawn from either A or B.

Because Alice and Bob live in different cities, they have limited communication bandwidth. They can send each other one integer at a time, where the value either falls within {0,…,n} or is drawn from the original A or B arrays. Each numeric transmission counts as a "communication" between Alice and Bob. One goal of this problem is to minimize the number of communications needed to compute the median.

              Compute the combined median of A and B. Your algorithm should run in time and use  communications. Write your algorithm in pseudocode first. Then write the code to accomplish the computing. (Hint: you will do sorting first, it is required to use heapsort).

               

Input:  is {61, 17, 30, 50, 83, 9}

 is {2, 27, 198, 25, 4, 18}

Read full article from Distributed Median problem - workdog的专栏 - 博客频道 - CSDN.NET