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

Question

引用 MIT handout 中的解决方案

我尝试自己找出解决方案，但遇到了困难，我相信我需要帮助才能理解以下几点。

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

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

我不明白最后两个参数为什么不简单地是 1，l 为什么分别是 max 和 min。

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 中的太多元素，无法成为中位数。

如果左 > 右，则二分查找将我们正在搜索的A段减少到什么都没有。切换 A 和 B 意味着我们开始搜索另一个数组。