題目：
實現(xiàn)int sqrt(int x)函數(shù)狮含。
計算并返回x的平方根表蝙，其中x 是非負(fù)整數(shù)乓旗。
由于返回類型是整數(shù)屿愚，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去穷遂。
示例 1:
輸入:4
輸出:2
示例 2:
輸入:8
輸出:2
說明:8 的平方根是 2.82842..., 由于返回類型是整數(shù)蚪黑，小數(shù)部分將被舍去忌穿。
思路：
典型的二分法
代碼：
解法一
public int mySqrt(int x) {
if(x <= 1)
return x;
int left = 1,right = x;
while(left <= right){
int mid = left + (right -left) / 2;
int sqrt = x / mid;
if(sqrt == mid)
return mid;
else if(sqrt < mid)
right = mid - 1;
else
left = mid + 1;
}
return right;
}
解法二：
public int mySqrt(int x) {
long r = x;
while (r*r > x)
r = (r + x / r) / 2;
return (int) r;
}
