在O(logn)中找到三个排序数组的中值

Question

通过搜索几分钟，我知道了基本的想法。

1. 设A、B和C是包含n个元素的排序数组。
2. 在每个数组中选择中间值，并将它们称为medA、medB和medC。
3. 在不失去通用性的情况下，假设medA > medB > medC。
4. 数组A中大于medA的元素不能成为三个数组的中值。同样，数组C中小于medC的元素不能，因此这些元素将被忽略。
5. 递归地重复步骤2-4 .

我的问题是，基本情况是什么？假设有很多基本情况，我用手测试了几个小时，但是我找不到正确的基例。而且，每一个递归步骤，三个数组的长度都会不同。步骤4是否工作，即使三个数组的长度是不同的？

Answer 1

该算法适用于两个大小相同但不是三个的排序数组。在一次迭代之后，您消除了A和C中的一半元素，但B没有变化，因此这些数组中的元素数不再相同，并且该方法不再适用。对于不同大小的数组，如果应用相同的方法，将从下半部和上半部移除不同数量的元素，因此其余元素的中值与原始数组的中值不相同。

尽管如此，您可以修改算法，在每次迭代的两端消除相同数量的元素，当一些数组非常小，一些非常大时，这是有效的。您还可以将其转换为查找k-th元素的问题，跟踪要丢弃的元素的数量，并在每次迭代时更改k的值。无论哪种情况，这都比两个数组的情况复杂得多。

还有一篇关于一般案例的文章：Median of 5 sorted arrays