​200亿个数字中找中位数，我看了几百篇题解，很少人知道这种解法

200亿个数字中找中位数，我看了几百篇题解，很少人知道这种解法

海量数据里面如何寻找一堆数字的中位数，是一道非常常见的面试题。据称，这个题目是腾讯前首席技术执行官Tony推崇的一个面试题，被加入的腾讯的面试题题库。今天我们就来讨论下这个题目，有一个存放着200亿个数字的文件，存放着32位整型，可能会有重复的数字，现在想从这堆数字中找到他们的中位数。注意，这个题目是只能用单机解决，并且内存只有512M。

我们也简单介绍一下。假如内存足够，我们当然希望在内存里面开一个数组或者一个字典Map，用来保存每一个数字与其出现次数的。可是在这个题目里面，我们并没有那么多的内存可以开辟这么大的内存空间。我们最常见的做法便是分桶算法了。什么是分桶算法呢？

什么是分桶呢？就是把若干的数字分到一个桶里面，对外界来说，只关心桶编号。举一个简单的例子，例如数字的范围是1到100万，但是我们只能开范围大小为100的数组，我们一开始先按照1万进行分桶，那么第一个桶就表示1到1万的数字，第二个桶就表示10001

到20000的数字，第三个桶就表示20001到30000的数据。对于外界来说，对于15000这个数字，并不关心他是多少，只关系它在第二个桶，于是把第二个桶的计数器增加一。

接下来我们能做什么呢？我们是不是可以根据这100个桶，统计出中位数在哪一个桶，即便我们并不知道具体数字是多少。接下来，我们就按照100进行分桶，再次缩小中位数的范围，最后我们再按照1进行分桶，就能找到最终的答案。但是今天我们要讨论的，是不能使用分桶算法！

但是这个题目不给使用分桶算法，那么我们就无从下手了么？今天我们来讲一讲，如何使用分治算法，二分法来解决这个题目。

对于大多数人来说，二分法不是用来查找具体的数值的么？怎么还能用来查询中位数了呢？今天我们就来讲讲二分法的妙用。

对于200亿个数字，假如我们假设中位数是100万，如果大于100万的数有50亿个，不就说明了中位数在1到100万之间么?相反，如果大于100万的数字有150亿个，也就说明了中位数大于100万。

假如大于100万的数字有50亿个，那么我们可以再次假设中位数是50万，再次扫描文件，看看大于50万的数字有多少个，假如是70亿个，那么我们再次假设中位数是25万。

按照上述方法，我们每次都用二分法，找到中位数，每次都扫描整个文件，最多需要扫描log(N)次文件。这种方法，对内存的依赖极小，不妨是一个好方法。

最后，除了分桶算法还有二分法，这个题目还有很多种不同的做法，如果你有兴趣，欢迎关注我，后面我们再继续分享这个题目的其他解法。更多这个题目的其他解法，欢迎到我的圈子里面讨论！

（此处已添加圈子卡片，请到今日头条客户端查看）