algorithm - Clog n的算法问题设计[C++代码]

Question

两个排序的整数数组，A[1..N]并按升序B[1..N]提供。

问：设计一个O(log N)-time算法来找出所有 2N 个整数的中位数。N 可能不是 2 的幂。

为了简单起见，我们可以假设O(1)算法返回m如下：

2^m < N <  2^m+1

我的问题：

1. N可能不是power of 2，是什么意思？（了解）
2. 我不知道如何更改输入并 在找到数组min和.maxAB

Answer 1

O(logN)您可以使用二分搜索风格的方法及时解决这个问题。考虑以下两个数组：

1 1 2 2 3
1 2 3 4 5

现在合并的中位数是：

1 1 1 2 2 2 3 3 4 5 => 2

让我们看看如何找到它。首先猜测中位数是每个数组的中心：

1 1 2 2 3 => 2
1 2 3 4 5 => 3

从逻辑上讲，我们知道组合中位数不可能小于2 或大于3。相反，它必须介于这两个值之间。所以我们可以丢弃第一个数组中小于2 的所有内容，以及第二个数组中大于3 的所有内容。这不会影响中位数的位置，因为我们在组合中位数的两侧丢弃了相同数量的元素. 从概念上讲，这给我们留下了：

2 2 3 => 2
1 2 3 => 2

现在我们已经有了一个一致的中值，但基本思想是不断丢弃两个数组中每个数组中的一半条目，直到我们得到一个中值。

该算法的性能与二分搜索一样好，即O(logN).