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 可能不是 2 的幂，这是什么意思？ (明白了)
2. 我不知道如何更改输入并使长度成为 2 的幂 在找到 min 和 max 之后来自数组 A 和 B 的元素。

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 2 3 => 2
1 2 3 => 2

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

此算法的性能与二分查找一样好，即 O(logN)。