7-2 两个有序序列的中位数 (25 分)

题目描述：

给定两个长度为n的有序序列A和B，本题要求时间复杂度为O(logn)的算法，找出两个序列的中位数。

输入格式：

第一行输入一个整数n，表示序列的长度。

第二行输入n个整数，表示序列A。

第三行输入n个整数，表示序列B。

输出格式：

输出一个整数，表示两个序列的中位数。

输入样例：

5
1 3 5 7 9
2 4 6 8 10

输出样例：

5

解题思路：

中位数的定义是：将一个集合分成两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。根据这个定义，我们可以将两个有序序列分别划分成两个长度相等的子集，使得一个子集中的元素总是大于另一个子集中的元素。假设序列A和序列B的长度都为n，我们可以将序列A和序列B分别划分成两个长度为n/2的子序列，分别为A1、A2和B1、B2。如果A1的中位数小于B1的中位数，那么A1中的元素肯定都小于两个序列的中位数，因此可以将A1中的元素全部舍去，将A2和B1、B2组成新的序列，继续进行划分。如果A1的中位数大于B1的中位数，那么B1中的元素肯定都小于两个序列的中位数，因此可以将B1中的元素全部舍去，将A1、A2和B2组成新的序列，继续进行划分。如果A1的中位数等于B1的中位数，那么A1和B1中的元素都小于两个序列的中位数，因此可以将A1、B1和A2、B2组成新的序列，继续进行划分。每次划分后，序列的长度都会减半，因此时间复杂度为O(logn)。

代码实现：