原题
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例1：
输入： 4
输出： 2
示例2：
输入： 8
输出： 2
说明： 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
解法
思想
二分法
代码
class Solution {
public int mySqrt(int x) {
//为了防止end * end 超过int范围，这里统一使用使用long
long longx = x;
long start = 0;
long end = x/2;
long mid;
while(start<=end){
mid = (end+start)/2;
if(mid*mid == longx) return (int)mid;
if(mid*mid < longx) {
start = mid + 1;
if(start*start>longx) return (int)mid;
}
else if(mid*mid > longx) {
end = mid - 1;
if(end*end<longx) return (int)end;
}
}
return (int)start;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode69-x%e7%9a%84%e5%b9%b3%e6%96%b9%e6%a0%b9/
