问题描述：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
//思路：典型的利用二分查找
//[l,r]中查找值为 sqrt 的元素。
//同时 sqrt 的值和l、r 有关，而l，r 是不断变化的
class Solution {
public int mySqrt(int x) {
if(x<=1){
return x;
}
int l = 0;
int r = x;
while(l<=r){
int mid = (r-l)/2 + l;
int sqrt = x/mid;
if(sqrt == mid){
return mid;
}else if(sqrt > mid){
l = mid + 1;
}else{
assert sqrt < mid;
r = mid - 1;
}
}
//循环结束时 l > r,这里忽略小数部分。
return r;
}
}
参考：
标签：int,mid,整数,sqrt,平方根,小数 From： https://www.cnblogs.com/i9code/p/18000333