二分搜索左右索引以查找两个排序数组的中位数

Question

两个排序数组

A

和

B

分别具有大小

l

和

m

。我们的任务是找到这两个排序数组组合的中位数。假设组合数组的长度为

n

即

n = l + m

。根据定义，中位数将大于一半元素并小于另一半。

假设

A[i]

是中位数。那么由于 A 已排序所以

                            A[i] >= A[k] for all k = 0 to i - 1

并且它也将大于 j = ⌈n/2⌉- (i - 1)

 中的 

B 元素，因为

i + j

必须等于

⌈n/2⌉

。

                      A[i] >= B[k] for all k = 0 to ⌈n/2⌉- (i - 1)

如果

A[i]

不是中位数，则取决于

A[i]

是否更大 或小于

B[j]

和

B[j + 1]

，您就知道

A[i]

大于或小于中位数。

因此可以在这里对 A[i] 进行二分查找。以下是我从网站找到的伪代码：

                MEDIAN-SEARCH(A[1 . . l], B[1 . . m], left,right)

                 if left > right:
                   MEDIAN-SEARCH(B, A, max(1, ⌈n/2⌉ − l), min(m, ⌈n/2⌉))

                 i = ⌊(left + right)/2⌋

                 j = ⌈n/2⌉ - i

                 if (j = 0 or A[i] > B[j]) and (j = m or A[i] <= B[j + 1])
                   return A[i]

                 else if (j = 0 or A[i] > B[j]) and j != m and A[i] > B[j + 1]
                   return MEDIAN-SEARCH(A, B, left, i − 1)

                 else
                   return MEDIAN-SEARCH(A, B, i + 1, right)

查找中位数的初始调用将是

                 MEDIAN-SEARCH(A[1..l], B[1..m], max(1, ⌈n/2⌉ − m), min(l, ⌈n/2⌉))         

我的问题是：

1. 我无法直观地想象上面的代码中如何使用

   left

   和

   right

   初始值。
2. 算法的时间复杂度是多少？会是

   log O(N)

   吗？还是会

   log O(max(l, m))

   ？

Answer 1

如果您的任务是找到中位数，您可以合并数组（您已经这样做了），对整个事物进行排序，然后使用以下代码找到中间项：

//pretend your combined array in arrCombined
if (arrCombined.size() % 2 == 1) {
    cout << arrCombined[arrCombined.size()/2];
}
else {
    cout << (arrCombined[arrCombined.size()/2] + arrCombined[arrCombined.size()/2 - 1])/2;
}

对于你的问题，如果你无法理解第1点，那么实际上，左和右是整数，保存了你要搜索的内容的左和右范围，这意味着左是基于你的消除的最左边的可能值，右是最右边的可能值。至于你的第二个问题，正如 trincot 在评论中已经说过的， O(log𝑛) = O(log(max(𝑙, 𝑚))，所以你可能需要重新表述你需要的内容。