完善程序-2解析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
using namespace std;
const int MAXN=1000;
int n,i,lbound,rbound,mid,m,countt;
int x[MAXN];
int main(){
    //n是数据个数，m是数据最大值
    cin>>n>>m;
    //输入n个整数
    for ( i = 0; i < n; i++)
        cin>>x[i];
    lbound=0;  //lbound是左边界，起始是0
    rbound=m;  //rbound是右边界，起始是m
    while(lbound<rbound){
        mid=(lbound+rbound)/2;
        
        countt=0; //记录在数组里有多少数大于mid
        for ( i = 0; i < n; i++){
            if(x[i]>mid) 
            countt++;
        }
        if(countt>n/2) //如果countt大于n/2，说明中位数在mid+1,rbound之间
            lbound=mid+1;
            else
            rbound=mid;
    }
    cout << rbound << endl;
    return 0;
}