1.实践题目：（第三题）两个有序序列的中位数：
2.问题描述：这道题要求在两个等长的非降序序列中求出其并集的中位数，老师还加了时间复杂度不超过logn的要求。
3.算法描述：开始时我和队友用的是排序法现将并集求出来，但是的时间复杂度就是O（N）了， 后来查找了资料看了其他的思路后，最后用的方法是比较两个序列的中位数的方法，也就是二分法；
（1）两个数列中位数若一样，则该数就是所求中位数；
（2）若某一个中位数大， 则选择该中位数左边的数与另一数列中位数右边的数组成新的两个序列继续比较中位数；
（3）在第（2）种情况下，为保持新的两个数列等长，需要判断序列长度，若是奇数，则两个序列取半时，都把中位数取进来，若是偶数，则中位数小的一边取半时不取中位数；
e.g.图片中输入样例一中第一次取半为1,3,5以及4,5,6;
样例二第一次取半为1,1,1以及-50,0,2;
（4）最后两个序列都只剩下一个数时，还不相等，则较小的数为中位数。
我的代码：
1 #include <iostream> 2 using namespace std; 3 4 5 void Merge(int a[], int b[], int aLeft, int aRight, int bLeft, int bRight) 6 { 7 int aMiddle = (aLeft + aRight) / 2, bMiddle = (bLeft + bRight) / 2; 8 if (a[aMiddle] == b[bMiddle])//两个数列中位数一样，该数就是所求中位数 9 { 10 cout << a[aMiddle]; 11 return; 12 } 13 else if (aLeft == aRight)//两个序列都只剩下一个数，则较小的一个数为中位数 14 { 15 if (a[aMiddle] < b[bMiddle]) cout << a[aMiddle]; 16 else cout << b[bMiddle]; 17 exit(0); 18 } 19 else if (a[aMiddle] < b[bMiddle]) 20 {//两个中位数中较大的，其左边的数与较小的中位数右边的数，组成新的两个序列继续比较中位数 21 if ((aRight - aLeft) % 2 == 1) 22 { 23 Merge(a, b, aMiddle + 1, aRight, bLeft, bMiddle); 24 } 25 else 26 { 27 Merge(a, b, aMiddle, aRight, bLeft, bMiddle); 28 } 29 } 30 else// a[aMiddle] > b[bMiddle] 31 { 32 if ((aRight - aLeft) % 2 == 1)// 33 { 34 Merge(a, b, aLeft, aMiddle, bMiddle + 1, bRight); 35 } 36 else 37 { 38 Merge(a, b, aLeft, aMiddle, bMiddle, bRight); 39 } 40 } 41 } 42 43 44 int main() 45 { 46 int N; 47 cin >> N; 48 int* a = new int[N];//a,b,为两段等长的非降序序列 49 int* b = new int[N]; 50 for (int i = 0; i < N; i++) 51 { 52 cin >> a[i]; 53 } 54 for (int j = 0; j < N; j++) 55 { 56 cin >> b[j]; 57 } 58 Merge(a, b, 0, N - 1, 0, N - 1); 59 return 0; 60 }
4.算法时间及空间复杂度分析：
最好情况下比较一次中位数相等即可。
最坏情况下，一直比较到两边都只剩一个数，开始时一个序列有N个数，用二分法不断取半之后到N/2, N/4, N/8...直到1，比较次数为（1 + logN）（以2为底）则时间复杂度为O(logN)。
5.心得体会：一开始就是按照以前的习惯为了速度无脑排序，一口气做下来，却忽略了时间复杂度的需求，没有需求时也没有想过要写的复杂度低一些。这次实践课让我体会到分治法的高效性，以大化小却不变形式 ，往往可以更快得到问题的解，写眼熟的算法前也要思考下能不能用上新的知识，用更好的算法思想改进以前的思路。