---

 

思路：

设定两个升序序列分别为A与B，中位数分别为a和b。

1）若a = b,则a或b即为所求中位数，算法结束。

2）若a<b,则舍弃序列A中较小的一半，同时舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两此舍弃的长度相等。

3）若a > b,则舍弃序列A中较大的一半，同时舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。

在保留的两个升序序列中，重复过程1，2，3，直到两个序列中均含有一个元素时为止，较小者即为所求的中位数。

---

 

代码如下：

 1 #include<iostream>
 2 
 3 int M_Search(int A[], int B[], int n) {
 4     int s1 = 0, s2 = 0, d1 = n - 1, d2 = n - 1, m1, m2;  //首位数，末位数，中位数
 5     while (s1 != d1 || s2 != d2) {
 6         m1 = (s1 + d1) / 2;
 7         m2 = (s2 + d2) / 2;
 8         if (A[m1] == B[m2]) {
 9             return A[m1];
10         }
11         else if (A[m1] < B[m2]) {
12             if ((m1 + d1) % 2 == 0) {
13                 s1 = m1;
14                 d2 = m2;
15             }
16             else {
17                 s1 = m1 + 1;
18                 d2 = m2;
19             }
20         }
21         else {
22             if ((s2 + d2) % 2 == 0) {
23                 d1 = m1;
24                 s2 = m2;
25             }
26             else {
27                 d1 = m1;
28                 s2 = m2 + 1;
29             }
30 
31         }
32     }
33     return A[s1] < A[s2] ? A[s1] : B[s2];
34 }
35 int main() {
36     int A[6] = { 2,4,6,8,10,12 };
37     int B[6] = { 1,3,5,7,9,11 };
38     int mid = M_Search(A, B, 6);
39     std::cout << mid << std::endl;
40 }