1 完善程序 (单选题 ，每小题3分，共30分)
中位数 median
给定 n（n为奇数且小于 1000）个整数，整数的范围在 0∼m(0<m<2^31) 之间，请使用二分法求这 n个整数的中位数。所谓中位数，是指将这 n个数排序之后，排在正中间的数。(第五空 2 分，其余 3 分)
01 #include <iostream>
02 using namespace std;
03
04 const int MAXN = 1000;
05 int n, i, lbound, rbound, mid, m, count;
06 int x[MAXN];
07
08 int main()
09 {
10 cin >> n >> m;
11 for (i = 0; i < n; i++)
12 cin >> x[i];
13 lbound = 0;
14 rbound = m;
15 while (①)
16 {
17 mid = (lbound + rbound) / 2;
18 ②;
19 for (i = 0; i < n; i++)
20 if (③)
21 ④;
22 if (count > n / 2)
23 lbound = mid + 1;
24 else
25 ⑤;
26 cout << mid << " " << lbound << " " << rbound << " " << count << endl;
27 }
28 cout << rbound << endl;
29 return (0);
30 }
1 ①处应填( )
2 ②处应填( )
3 ③处应填( )
4 ④处应填( )
5 ⑤处应填( )
2 相关知识点
二分答案
二分答案顾名思义，它用二分的方法枚举答案，并且枚举时判断这个答案是否可行
直接对答案进行枚举查找，接着判断答案是否合法。如果合法，就将答案二分进一步靠近，如果不合法，就接着二分缩小判断。这样就可以大大的减少时间。
二分中有时可以得可行得答案，但不是最大的，继续向右靠近，求出最大值
int ans = 1;int l = 1,r = 100000;//在1~100000之间的整数枚举 while(l <= r){int m = l + (r - l) / 2;if(check(m)){//满足 则进行向右缩小范围 看看有没有更大的 ans = m;//可能多次赋值 最后一定是可能的最大值 l = m + 1;}else{//不满足缩小边长 向左缩小范围 用更小边长继续尝试 r = m - 1;} }
二分找边界
//左闭右闭 while left right 最终left=right+1
while(left<=right) left = mid + 1; right =mid-1;
//左闭右开 while left right 最终left=right
while(left<right) left = mid + 1; right =mid;
//左开右闭 while left right 最终left=right
while(left<right) left=mid; right=mid-1;
//左开右开 while left right 最终left=right-1
while(left+1<right) left=mid; right=mid;
二分查找时间复杂度
二分查找每次都缩小或扩大为原来的一半，所以也是Olog(n)
3 思路分析
1 在0~m范围内，二分枚举，把原来n个数分成2部分
2 统计其中一部分的个数，本题统计大于mid数的个数，计入变量count
3 如果count>n/2 ,即count大于n的一半，向右缩小范围，下次计算让count变小
4 否则 如果count<=n/2 ,向左缩小范围，下次计算让count变大一些
5 上面3和4步骤的目标是让count=n/2,找到最中间的数
1 ①处应填( lbound < rbound )
分析
根据
//左闭右闭 while left right 最终left=right+1
while(left<=right) left = mid + 1; right =mid-1;
//左闭右开 while left right 最终left=right
while(left<right) left = mid + 1; right =mid;此处依赖第5题
由于lbound = mid + 1; 是左闭区间
由于第5题填rbound=mid; 是右开区间，所以 lbound < rbound
第5题填rbound=mid;的原因，请参考第5题解析
22 if (count > n / 2)
23 lbound = mid + 1;
24 else
25 ⑤;
2 ②处应填( count=0 )
分析
每次二分后，需要重新计算大于mid的数的个数，所以需要先对count初始0
不初始0的话，上次二分的计算结果会对本次产生影响，count值不对
3 ③处应填( x[i]>mid )
分析
循环统计大于mid的数个数，如果x[i]>mid ,count累加，count++
19 for (i = 0; i < n; i++)
20 if (③)
21 ④;
4 ④处应填( count++ )
分析
参考第3填
5 ⑤处应填( rbound )
分析
由于输出结果是rbound，count=n/2在rbound这里赋值
rbound=mid;此时计算出来mid是要找的中位数，如果rbound=mid-1的话，rbound会比实际答案小1
22 if (count > n / 2)
23 lbound = mid + 1;
24 else
25 ⑤;28 cout << rbound << endl;
