如何找到两个排序数组之间的中值？

Question

我正在研究一个有竞争力的编程问题，我们试图找到两个排序数组的中值。最优算法是在两个数组之间执行二进制搜索和识别分裂点( i和j )。

我自己很难找到解决方案。我不明白最初的逻辑。到目前为止，我将遵循我对这个问题的看法。

中值的概念是将给定的数组划分为两个集合。在合并两个给定的数组之后，考虑一个假设的left数组和一个假设的right数组。这两个数组的长度相同。

我们知道，给定这两个假设数组的中值都是[max(left) + min(right)]/2。到目前为止，这是合理的。但是这里的问题是现在知道如何构造left和right数组。

我们可以在ArrayA上选择一个分裂点作为i，在ArrayB上选择一个分裂点作为j。注意，len(ArrayB[:j] + ArrayB[:i]) == len(ArrayB[j:] +ArrayB[i:])。

现在我们只需要找到切点。我们可以尝试所有分裂点i，j，使它们满足中值条件。不过，这实际上是O(m*n) where M is size of ArrayB and where N is size of ArrayA。

我不知道如何用我的思路找到二进制搜索解决方案。如果有人能给我指点-那就太棒了。

Answer 1

这是我想出的办法。

首先，我们知道得到的数组将包含N+M元素，这意味着左边部分将包含(N+M)/2元素，右边部分也将包含(N+M)/2元素。让我们将结果数组表示为和，并表示其一个部件的大小为PartSize。

在数组A上执行二进制搜索操作。这种二进制搜索的范围将是，N。此二进制搜索操作将帮助您确定数组的元素数--将构成结果数组的左部分。

现在，假设我们正在测试值i。如果数组的i元素A应该包含在结果数组的左边部分，这意味着在第一部分中必须包含来自数组B的j = PartSize - i元素。我们有以下可能性：

• j > M，这是一个无效的状态。在这种情况下，这意味着我们仍然需要从数组A中选择更多的元素，因此我们的新二进制搜索范围为i + 1，N。
• j <= M & Ai+1 < Bj这是一个棘手的情况。想想看。如果数组A中的下一个元素小于数组B中的元素j，这意味着元素Ai+1应该位于左侧，而不是元素BjE 255。在本例中，我们的新二进制搜索范围为i+1，N。
• j <= M & Ai > Bj+1 -这与前面的情况非常接近。如果数组B中的下一个元素小于数组A中的元素i，则元素Bj+1应该位于左侧，而不是元素Aie 275。在本例中，我们的新二进制搜索范围为，i-1.
• j <= M & Ai+1 >= Bj & Ai <= Bj+1 --这是最佳情况，您终于找到了答案。

二进制搜索操作完成后，您成功地计算了i和j，现在您可以很容易地找到中位数的值。这里需要处理一些情况，具体取决于N+M是奇数还是偶数。

希望能帮上忙！