在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]

案例2：

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

案例3：

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

案例4：

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

所需时间:O(对数n)。有什么想法吗？

Answer 1

看看这两个数组的中间。假设一个值更小，另一个值更大。

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

清洗并重复，直到每个数组中只剩下一个元素。把这两个中较小的一个还回去。

如果两个中间值是相同的，那么任意选择。

信贷： 比尔·李的博客

Answer 2

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

注意:如果在第一个数组中找不到中位数，那么在第二个数组中开始初始搜索。这不会对复杂性产生影响。

Answer 3

所以，n= 4，a= 1，2，3，4，b= 3，4，5，6

你知道基于n的结果数组中的第k个位置，它等于n。结果n元素可以在第一个数组中，也可以在第二个数组中。让我们先假设这个元素在第一个数组中，然后进行二进制搜索，从l，r开始，在l= 0，r=3处取中间元素；因此，取中间元素，您知道同一个数组中有多少个元素较小，即中间- 1。知道中间-1元素较少，并且知道您需要第二个数组中的n-(中间-1)元素，才能使第二个数组中的n-(中间-1)元素更小、更大。如果这更大，而previos元素更小，这就是你所需要的，如果它更大，以前也更大，我们需要L=中间，如果它较小r=中间。而不是对第二个数组执行同样的操作，以防您无法首先找到解决方案。总日志(N)+ log(n)