举例如下:
A:1、2、8、9、10
B:1、2、3、4、11
第一次:
A:1、2、{8}、9、10
B:1、2、{3}、4、11
因为8>3,所以第二次:
A:1、{2}、8
B:3、{4}、11
因为2<4,所以第三次:
A:{2}、8
B:{3}、4
因为2<3,所以第四次:
A:{8}
B:{3}
再举一个简单的例子:
A: 1 3 5 7 9
B: 2 4 6 8 10
结果我们都知道是5(下中位数)。
第一步:取5 和 6比较,发现5<6,则在 7 9 2 4中寻找吗?
偶数的情况类似:
A: 1 3 5 7 9 11
B: 2 4 6 8 10 12
第一步:取5 和 6比较,发现5<6,则在 7 9 11 2 4中寻找吗?
个人认为取一半的时候一定需要包含用于比较的两个中位数(无论奇偶)。
就是说上面的两个例子第一步之后:
在A:5 7 9 B:2 4 6中继续找
在A:5 7 9 11 B:2 4 6中继续找
但这样导致新的问题是:新的数组A和B数字个数不一致了!
办法是: 在递归的过程中,当数组中的元素是偶数时,在一个数组中取上中位数,在另一个数组中取下中位数,并且在整个过程中保持不变。在哪个数组中去上中位数,就一直在那个数组中取上中位数,反之亦然。奇数时的情形依旧。
这也就解释了为什么代码中a[mid]<b[mid] 的时候,a数组的开始位置会是: a[length-mid-1]