arrays - 在 O(logN) 中找到两个排序数组的合并数组的中位数？

Question

引用 MIT handout 中的解决方案

我试图自己找出解决方案，但卡住了，我认为我需要帮助来理解以下几点。

1. 在解决方案中使用的函数头中

   中值搜索 (A[1 . . l], B[1 . . m], max(1,n/2 − m), min(l, n/2))

我不明白最后两个参数为什么不是简单的 1，l 为什么分别是最大值和最小值。

1. 在伪代码中

   如果左 > 右

   如果达到上述条件，为什么要切换A和B数组。

谢谢你。

Answer 1

在

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

max 和 min 调用限制了我们正在搜索的 A 区域。我们可以提前知道，如果一个数在A中小于ceil(n/2)-m的位置，那么A<的元素过多 大于它，因为它是中位数。类似地，ceil(n/2) 之后位置的数字大于 A 的太多元素而不能成为中位数。

如果 left > right，则二分搜索将我们正在搜索的 A 段减少为空。切换 A 和 B 意味着我们开始搜索另一个数组。