Ider � 二分查找法的实现和应用(进阶篇)

找出多个服务器中第k个数

问题的描述是这样的：

在多个服务器上每个服务器都有一批数，每个服务器直接并不知道对方的内容，你有一个主机可以联到每个服务器上去请求数据，现在要求从这些服务器的数据中找出第k小的数。

一个常用的方法就是在主机上创建一个存储k个数据堆结构然后获取每个服务器的数据并与堆中数据进行比较和交换。最后我们就可以得到所要的数据。

该问题其实可视为是"找出两个有序数组中第k个数"的多服务器大规模变体。一般诸如Google，Facebook，Microsoft这样的大公司会比较喜欢问（我有个朋友面试FB时就问到了这个问题）。

问题并没有表明每个服务器下的数是否有序的，不过我们可以让每个服务器对自己的数据进行排序，这是同步的，所以最多是O(n log n)的时间。在主机上则维护一个k大的有序数组，然后于每个服务器之间进行进行"找出两个有序数组中第k个数"，之后保留下新的前k个数。其复杂度应该是O(n log k)，其中n是服务器数量，k是所求目标。加上服务器排序时间，基本可以维持在O(n log n)的级别。

Read full article from Ider � 二分查找法的实现和应用(进阶篇)