3、X[0:n-1]和Y[0:n-1]为两个数组，每个数组中的n个元素都已经从小到大排序，试设计一个O(logn)的分（减）治算法，找出X和Y中2n个数的中位数。（注：2n个数的中位数是排序后第n个和第n+1个数）请写出（1）叙述算法设计思路；（2）写出算法伪代码；（3）分析算法的时间复杂性.

(1) 算法设计思路：

首先，我们可以将问题转化为找到两个数组中第k小的数，其中k为n的中间位置。我们可以通过比较两个数组中的中间位置元素的大小，来决定哪个数组中的前一半元素可以被排除掉。具体来说，假设X和Y的长度都为n，我们可以比较X[n/2-1]和Y[n/2-1]的大小，如果X[n/2-1]小于Y[n/2-1]，那么X[0:n/2-1]中的元素都可以被排除掉，因为它们肯定不是第k小的数。同样地，如果Y[n/2-1]小于X[n/2-1]，那么Y[0:n/2-1]中的元素都可以被排除掉。如果X[n/2-1]等于Y[n/2-1]，那么它们中任意一个数组的前一半元素都可以被排除掉。

通过这种方式，我们可以将问题的规模缩小一半，然后递归地解决子问题，直到问题的规模缩小到1。此时，我们就找到了第k小的数。

(2) 算法伪代码：

def find_kth(X, Y, k):
n = len(X)
if n == 1:
return min(X[0], Y[0])
mid = n // 2
if X[mid-1] < Y[mid-1]:
return find_kth(X[mid:], Y, k-mid)
else:
return find_kth(X, Y[mid:], k-mid)

def find_median(X, Y):
n = len(X)
k = n // 2
if n % 2 == 0:
return (find_kth(X, Y, k) + find_kth(X, Y, k+1)) / 2
else:
return find_kth(X, Y, k+1)

(3) 时间复杂性分析：

每次递归都会将问题的规模缩小一半，因此递归的深度为O(logn)。每次递归需要比较两个数组的中间位置元素的大小，这需要O(1)的时间。因此，总时间复杂度为O(logn)。