arrays - 在leetcode中的两个排序数组中找到K以找到中位数的算法是什么

Question

solution在两个排序数组中实现查找中位数非常棒。但是，我仍然对计算 K

的代码感到很困惑

var aMid = aLength * k / (aLength + bLength)
var bMid = k - aMid - 1

我想这是这个算法的关键部分，我真的不知道为什么要这样计算。更清楚地解释我的意思，核心逻辑是分而治之，考虑到不同大小 list应该进行不同的划分。我想知道为什么这个公式运行得很好。

谁能给我一些关于它的见解。我搜索了很多在线文档，很难找到很好地解释这部分的 Material 。

提前致谢

Answer 1

该链接显示了计算每个数组中比较点的两种不同方法:一种始终使用 k/2，即使该数组没有那么多元素；另一种始终使用 k/2，即使该数组没有那么多元素；另一个(你引用的)试图根据数组的大小分配比较点。

从这两个例子可以看出，这两个例子都不是最优的，你如何计算比较点并没有太大区别，只要两个分量的大小在 K 中通常是线性的(使用 a例如，比较点之一的固定大小 5 将不起作用。)

该算法在每次迭代中通过 aMid 或 bMid 有效地减小了问题的大小。理想情况下，问题规模会减少 k/2；如果两个数组至少有 k/2 个成员，这就是你应该使用的计算。如果一个人有两个少数成员，您可以将数组的比较点设置为它的最后一个元素，并计算另一个比较点，以便总数为 k - 1。如果您最终丢弃某个数组中的所有元素，您然后可以立即返回另一个数组的元素 k。

该策略通常会比您链接中的任何一个建议执行更少的迭代，但它仍然是 O(log k)。