在O(logn)时间复杂度内找到合并数组的中间元素

Question

我们有两个大小相同的已排序数组，分别称为a和b。

如何在由a和b合并后的已排序数组中找到中间元素？

Example:

n = 4
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

merged = [1, 2, 3, 3, 4, 4, 5, 6]
mid_element = merged[(0 + merged.length - 1) / 2] = merged[3] = 3

更复杂的案例：

案例1：

a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

案例二：

a = [1, 2, 3, 4, 8]
b = [3, 4, 5, 6, 7]

第三种情况：

a = [1, 2, 3, 4, 8]
b = [0, 4, 5, 6, 7]

案例4：

a = [1, 3, 5, 7]
b = [2, 4, 6, 8]

时间复杂度为O(log n)。有什么想法吗？

- SiLent SoNG

---

你能使用集合包吗？如果可以的话，你可以使用SortedSet实现TreeSet并获取中间元素。 - YoK

@Yok：您是说将数组复制到TreeSet中吗？那样至少会是O（N）。 - SiLent SoNG

Answer 1

看一下两个数组的中间值。假设一个值比另一个大。

舍弃具有较小值的数组的低半部分。舍弃具有较高值的数组的上半部分。现在我们只剩下了开始的一半。

反复操作，直到每个数组只剩下一个元素。返回这两个元素中较小的一个。

如果两个中间值相同，则任意选择。

来源: Bill Li's blog

- Anurag

---

+1 给出信用，尽管 Bill Li 自己并没有给出任何信用（这个问题可能来自一些旧的算法教材）。 - Dimitris Andreou

Answer 2

非常有趣的任务。我不确定O(logn)，但对于我来说，O((logn)^2)的解决方案是显而易见的。 如果您知道第一个数组中某个元素的位置，则可以找到两个数组中较小元素的数量，然后加上这个值（您已经知道第一个数组中有多少较小的元素，并且可以使用二分查找找到第二个数组中较小元素的计数 - 因此只需将这两个数字相加）。因此，如果您知道两个数组中较小元素的数量小于N，则应查看第一个数组的上半部分，否则应移动到下半部分。因此，您将获得具有内部二进制搜索的一般二进制搜索。总体复杂度将为O((logn)^2)

注意：如果在第一个数组中找不到中位数，则从第二个数组开始进行初始搜索。这不会影响复杂性

- DixonD

---

你能详细解释一下吗？ - SiLent SoNG

Answer 3

假设有n = 4，a = [1, 2, 3, 4]和b = [3, 4, 5, 6]

你提前知道结果数组中的第k个位置，该位置等于n。 结果的第n个元素可能在第一个数组或第二个数组中。 首先假设该元素在第一个数组中， 从[l，r]中取中间元素进行二分查找，初始时l = 0，r = 3; 通过取中间元素，您知道相同数组中较小的元素数量，即middle - 1。 知道middle-1个元素较小，并且知道需要第n个元素，您可以从第二个数组中选择[n - (middle-1)]个元素来比较大小。如果它更大且前一个元素更小，则是所需的，如果它更大且前一个元素也更大，则需要L = middle，如果它更小，则r = middle。 如果在第一个数组中没有找到解决方案，则对第二个数组执行相同的操作。 总共log（n）+ log（n）

- Roman Dzhabarov