有序数组中找中位数

题目：两个有序数组a和b，大小都是n，寻找这两个数组合并后的中位数。时间复杂度为o(logn)。

中位数：如果数组的个数是奇数，那么中位数的值就是有序时处于中间的数；如果数组个数是偶数的，那么就是有序时中间两个数的平均值。

方法一：合并时计数

使用merge sort时的merge操作，比较两个数组时候计数，当计数达到n时，就可以得到中位数，在归并的数组中，中位数为下标n-1和n的两个数的平均值。

时间复杂度o(n)。

方法二：比较两个数组的中位数

ar1[]和ar2[]为输入的数组

算法过程：

1.得到数组ar1和ar2的中位数m1和m2

2.如果m1==m2，则完成，返回m1或者m2

3.如果m1>m2，则中位数在下面两个子数组中

a) from first element of ar1 to m1 (ar1[0...|_n/2_|])

b) from m2 to last element of ar2 (ar2[|_n/2_|...n-1])

4.如果m1<m2，则中位数在下面两个子数组中

a) from m1 to last element of ar1 (ar1[|_n/2_|...n-1])

b) from first element of ar2 to m2 (ar2[0...|_n/2_|])

5.重复上面的过程，直到两个子数组的大小都变成2

6.如果两个子数组的大小都变成2，使用下面的式子得到中位数：median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

时间复杂度：o(logn)。

方法三：通过二分查找法来找中位数

基本思想是：假设ar1[i]是合并后的中位数，那么ar1[i]大于ar1[]中前i-1个数，且大于ar2[]中前j=n-i-1个数。通过ar1[i]和ar2[j]、ar2[j+1]两个数的比较，在ar1[i]的左边或者ar1[i]右边继续进行二分查找。对于两个数组 ar1[] 和ar2[], 先在 ar1[] 中做二分查找。如果在ar1[]中没找到中位数, 继续在ar2[]中查找。

算法流程：

1) 得到数组ar1[]最中间的数，假设下标为i.

2) 计算对应在数组ar2[]的下标j，j = n-i-1 

3) 如果 ar1[i] >= ar2[j] and ar1[i] <= ar2[j+1]，那么 ar1[i] 和 ar2[j] 就是两个中间元素，返回ar2[j] 和 ar1[i] 的平均值

4) 如果 ar1[i] 大于 ar2[j] 和 ar2[j+1] 那么在ar1[i]的左部分做二分查找(i.e., arr[left ... i-1])

5) 如果 ar1[i] 小于 ar2[j] 和 ar2[j+1] 那么在ar1[i]的右部分做二分查找(i.e., arr[i+1....right])

6) 如果到达数组ar1[]的边界(left or right)，则在数组ar2[]中做二分查找

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

http://www.cnblogs.com/luxiaoxun/archive/2012/09/13/2684054.html