计蒜课_二分法求平方根

 1 #include<iostream>
 2 using std::endl;
 3 using std::cout;
 4 using std::cin;
 5 inline bool isRes(long x,long y){//判断 x是否为y的平方根； 
 6     return (x*x==y)||((x*x<y)&&((x+1)*(x+1)>y));
 7 } 
 8 int sqrt(long x){
 9         long lit=0;
10         long big=x; 
11         long mid=(big+lit)/2;//mid<big&&mid>=lit; 
12         //每次循环开始之前保证，结果在[lit,big]中；
13         while(lit<=big){
14             //防止上界下界都无法改变，如（x==1)，而造成的死循环；
15             if(isRes(lit,x))              
16                return lit;
17             lit++;//修改下界； 
18 
19              //修改上下界；
20             mid=(lit+big)/2;
21             (mid*mid<x)?lit=mid:big=mid;  
22         } 
23 }
24 int main(){
25     int x;
26     while(cin>>x){
27         cout<<sqrt(x)<<endl;
28     }
29 }