实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
class Solution {
public:
static int mySqrt(int x) {
int i = 0, j = x / 2 + 1;
long long ans;
while (i <= j) {
ans = (i + j) / 2;
if (ans * ans == x) {
return ans;
} else if (ans * ans > x) {
j = ans - 1;
} else {
i = ans + 1;
}
}
return j;
}
};对分查找，注意选好上界