分治算法举例5页.docx

1 设X0：n-1和Y0：n-1为两个数组，每个数组中含有n个已排序好的数。试设计一个O(logn)时间的分治算法，找出X和Y的2n个数的中位数，并证明算法的时间复杂性为O(logn)。注：个数为奇数，则处于最中间位置的数；个数为偶数，则中间两个数据的平均数。解：利用二分查找思想：对于两个等长的数组，如果数组长度为奇数，令mid为数组的最中间元素的位置，则有Xmid，Ymid分别为两个数组的中位数，则存在以下情况：（1）如果XmidYmid，则两个数组合并后的中位数应该在X0 : mid和Ymid : n-1中查找；（3）如果Xmid=Ymid，则两个数组合并后的中位数就是Xmid或者Ymid另外考虑特殊情况：如果两个数组的长度为1，则无需比较大小，合并后数组的中位数即为两个数组元素的平均值。如果数组的长度为偶数，令mid为数组的中间两个元素的较小元素的位置，此时数组X的