题目： 两个有序序列的中位数 

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列,的中位数指A​(N−1)/2​​的值,即第⌊个数（A​0​​为第1个数）。

输入格式:

输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

题目需求：时间复杂度为 O（logN）

解题思路：在考虑时间复杂度之前，一开始考虑的是使用第三个数组去归并两个数组，结果显然无法满足时间复杂度的需求；
          结合二分查找法以及分治法的思想，对两个有序数组进行二分，通过不断比较中位数来求得；
          可以用调用递归的方法去解决

方法步骤：1）递归函数中的判断条件：当子数列仅剩一个数时，返回较小的数就是所求解；
          2）若当前ma > mb 下一次递归就取a左边的子数列和b右边的子数列，反之逆推；
          3）而且要保证两个数列的元素个数相同，若为偶数数列，则需要ma++或mb++；
代码：

 1 #include<iostream>
 2 using namespace std;
 3 int a[100001],b[100001];
 4 
 5 int find(int la, int lb, int ra, int rb) {
 6     if (la == ra && lb == rb) {
 7         return a[la] > b[lb] ? b[lb] : a[la];
 8     }
 9     
10     int ma = (la + ra) / 2;
11     int mb = (lb + rb) / 2;
12     
13     if (a[ma] < b[mb]) {
14         rb = mb;
15         if ((ra - la) % 2) {
16             ma++;
17         }
18         la = ma;
19     } else {
20         ra = ma;
21         if ((rb - lb) % 2) {
22             mb++;
23         }
24         lb = mb;
25     }
26      return find(la,lb,ra,rb);
27 }
28 
29 
30 int main() {
31     int N;
32     cin >> N;
33     
34     for (int i = 0; i < N; ++i) {
35         cin >> a[i];
36     }
37     for (int i = 0; i < N; ++i) {
38         cin >> b[i];
39     }
40     cout << find(0 , 0, N - 1, N - 1);
41     return 0;
42 }

View Code

 

算法分析：

     时间复杂度：二分查找：O（logN），输入数据：O(N),所以是O（logN）；

     空间复杂度：并没有借助辅助变量，所以为O(1);

 

心得体会：

     二分法虽然作用很大，但在实际运用中一定要先构思好左右两端是如何移动变换的，最好动手动笔，先画出示意图，这样更能便于代码书写。