求两个数组的中位数

求两个数组的中位数

博客分类：
• 算法

算法编程 

1,题目
有两个数组,均已经按升序排列好,编程序计算这两个数组的中位数
要求:要求时间复杂度O(lgn)   空间复杂度O(1)
例子:
数组A:{1,4,6,7,9}   B{2,3,5,8}     两数组合并后{1,2,3,4,5,6,7,8,9}   中位数就是中间的那个数: 5
2,方法:

对两个数组分别二分找解
对每个元素可以O(1)判断它在另外一个数组应该所在的位置，从而可以判断选大了还是小了，继续二分直到找到解为止

先二分第一个数组找解，可选区域为[0,4]。选中A[2]=6,6前面有两个元素，如果将其插入第二个数组，那么6如果是解，则必须前面有4-2=2个元素（排第三位）
通过比较前后元素发现6放在B中的第三位明显大了，需要更小的元素，这样就将下一次二分的区域减了一半.

在A和B中重复这个过程，直到找到解为止

3，3,扩展

M个长度为N的排序好的数组 求中位数
目前有两个比较好的算法

算法一
(1)取所有数组的最小值和最大值,求出全体的最大值和最小值min max 然后取m=(min+max)/2
(2)用m在所有数组中搜索 找到比m小的数的个数n1 若n1大于M*N/2 则mid=(min+mid)/2 否则mid=(mid+max)/2
(3)重复上述搜索一共循环log(max-min)次


算法二
(1)取所有数组的中值排序
弃掉这个最大值所在数组的后半部分和最小值所在数组的前半部分 再将这两个只剩一半的数组合并 O(N)
(2)从合并后的数组中找出中值插入到之前的中值排序数组里 o(logN)
(3)重复(1)(2),每次循环可以舍掉一个数组,一共需要循环M次