平方根
求平方根
https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c?tpId=196&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
//关键在与int整性的平方会溢出，需要用long型，如果用long型不够，可以使用BigInteger或者使用大数乘法等。
public static int sqrt (int x) {
// write code here
if(x<=0) return 0;
long left = 1;
long right = x;
//找出最后一个数平方小于等于x
while(left+1<right){
long mid = (right-left)/2+left;
if(mid*mid==x) {
return (int)mid;
}
else if(mid*mid < x) left = mid;
else right = mid-1;
}
if(x>=right*right) return (int)right;
else if(x>=left*left) return (int)left;
else return -1;//找不到
}