描述#
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
思路#
- 暴力无脑解法，从 1 开始自增求平方，结果大于 x 则输出该值减一
int mySqrt(int x){
for(long i=1;;i++) {
if(i*i > x)
return (int)i-1;
}
}
思路二#
- 在之前的基础上，把自增的跨度增大，查找宽范围，再递减查找最终值
int mySqrt(int x){
long first = 1;
for(;first < x;first *= 2)
if(first * first >= x)
break;
for(long second = first;;second--)
if(second * second <= x)
return second;
}