找出两个排序数组的数组合并在O（logN）的中位数？ [英] Finding the median of the merged array of two sorted arrays in O(logN)?

问题描述

指的解决方案present在<一个href=\"http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf\"相对=nofollow>讲义MIT

Refering to the solution present at MIT handout

我试图找出解决自己但卡住了，我相信我需要帮助了解以下几点：

I have tried to figure out the solution myself but have got stuck and I believe I need help to understand the following points.

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

1. In the function header used in the solution

MEDIAN -SEARCH（A [1 L]，B [1微米。。]，最大（1，N / 2 - 米），分钟（L，N / 2））

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

我不明白，最后的两个参数，为什么不干脆1,1为什么最大值和最小值分别为

I do not understand the last two arguments why not simply 1, l why the max and min respectively.

1. 在pseduo code

1. In the pseduo code

如果左>右

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

why do we switch A and B arrays if we reach the above condition.

感谢你。

推荐答案

那么，当

left > right

那么，这意味着平均不在A. present因此，它必须是B. present因此，我们切换。

then, it means median is not present in A. So, it must be present in B. Thus we switch.

例如，尝试制定出算法

A = [ 1, 5] and B = [2, 3, 4]. 

现在，答案是3。
最初（左，右）为（1,3）。然后它变成（1，1），然后（2，1）现在，我们切换A和B，并继续B上的过程，以获得答案。

Now, answer is 3. Initially (left, right) is (1, 3). Then it becomes (1, 1) and then (2, 1) now, we switch A and B and continue the procedure on B to get the answer.

这篇关于找出两个排序数组的数组合并在O（logN）的中位数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！