通信复杂度问题：确定双方手中所有数的中位数
这篇讲的是通信复杂度中一个经典问题的算法设计：两地的两个人各自持有一个数字集合，他们想用尽可能少的通信来共同确定两个集合合并后的中位数，而不是笨拙地传输全部数据。 作者从问题背景出发，清晰地展示了从“暴力传输”到“极精巧算法”的优化路径。最初，A把全部数据传给B，通信量是O(n)比特；随后，通过在区间上进行多轮二分查找，算法被优化至O(log²n)。文章的高潮在于将复杂度降至O(logn)的精妙改进。核心思路是让双方比较各自数列的中位数a和b，根据大小关系丢弃一半不可能成为答案的数据。但关键在于，双方不需要完整传输a和b的数值，而是从高位到低位逐位比较并发送比特。一旦某一位不同就能立即停止本轮比较；同时，由于数据集在每轮都被减半，之前比过的公共前缀位在未来轮次中可以直接跳过。这种逐位比较与信息复用，将总通信量压到了O(logn)。 文章不仅给出了算法，还从信息论角度推导了Ω(logn)的下界，完整勾勒出问题的解空间。其价值在于，通过一个看似简单的游戏，生动展现了通信复杂度的理论力量与算法设计的艺术。