1.題目描述
?
Implement int sqrt(int x).?Compute and return the square root of x.
LEETCODE。2.解法分析
很明顯,用二分搜索可解,但是需要防止溢出,所以中間結果和上界下界都要用long long 來保存。
class Solution {
public:
int sqrt(int x) {// Start typing your C/C++ solution below
// DO NOT write int main() function
if(x<0)return -1;if(x<4)return x>0?1:0;long long rmin=0;long long rmax=x/2;long long rmid;while(rmin<rmax)
{rmid=(rmin+rmax)/2;if((rmid*rmid)==x)return rmid;if((rmid*rmid)<x)rmin=rmid+1;
else rmax=rmid-1;
}int result=rmin;
while(result*result>x)result--;
return result;
}};