两个排序数组的中间值

Question

对于计算两个排序数组的中位数，我无法理解下面的基本情况5和6。N和M是两个数组的长度。

基大小写:较小的数组只有一个元素

案例0: n= 0，M=2 案例1: n= 1，M= 1。 案例2: n= 1，M是奇数 案例3: n= 1，M是偶数

较小的数组只有两个元素。

案例4: n= 2，M=2 案例5: n= 2，M为奇数 例6: n= 2，M是偶数

案例0:在第一个数组中没有元素，返回第二个数组的中值。如果第二个数组也是空的，返回-1。

例1:两个数组中只有一个元素，因此输出A和B的平均值。

例2: n= 1，M是奇数，让B5 = {5，10，12，15，20}首先找到B[]的中间元素，对于上面的数组是12。有以下四个子案例。

…2.1如果A小于10，中位数为10和12。 …2.2如果A介于10至12之间，则中位数为A和12的平均数。 …2.3如果A介于12至15之间，则中位数为12和A的平均数。 …2.4如果A大于15，中位数为12和15。

在所有的子案例中，我们发现12是固定的。因此，我们需要找到B/2-1，B/2+ 1，A0的中值，并取其与B/2的平均值。

案例3: n= 1，M是偶数

设B4 = {5，10，12，15}

首先在B[]中找到中间项，在上面的示例中为10和12。有以下三个子案例。

…3.1如果A小于10，则中位数为10。 …3.2如果A介于10至12之间，则中位数为A。 …3.3如A大于12，则中位数为12。

因此，在这种情况下，求出三种元素B/2-1，B/2和A0的中值。

例4: n= 2，M=2共有四个元素。所以我们找到了4种元素的中位数。

案例5: n= 2，M为奇数

设B5 = {5，10，12，15，20}

中位数由以下三个元素的中位数: BM/2，max(A，BM/2-1)，min(A1，BM/2 + 1)。

例6: n= 2，M是偶数

设B4 = {5，10，12，15}

中位数由以下四个元素的中位数: BM/2，BM/2-1，max(A，BM/2-2)，min(A1，BM/2 + 1)

为了理解两个排序数组的中值，我参考了下面的URL。http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/

Answer 1

最简单的方法是.用铅笔和纸。绘制两个数字列表(都是短的.)，一个有奇数的元素，另一个是偶数。现在，非常仔细地查看案例5和案例6的解决方案之间的细微但重要的差异。

由于所呈现的逻辑多次使用MAX()函数，因此您的铅笔和纸张构造情况首先是一个，然后是MAX()的两个参数中的另一个是“最大的”。

在十五分钟左右的时间里，用那张纸和那支二号铅笔，你就能让自己相信算法有(或者，不是吗？)工作。

..。(是的，这是一个非常严肃的建议。这就是，，我是如何解决这些问题的！)