Sqrt(x)——LeetCode
2689 ワード
Implement
Compute and return the square root of x.
実现してひとつのintの根を求めます.
問題を解く構想:二分.
int sqrt(int x) . Compute and return the square root of x.
実现してひとつのintの根を求めます.
問題を解く構想:二分.
public class Solution {
public int mySqrt(int x) {
if (x <= 0) {
return 0;
}
if (x <= 3) {
return 1;
}
long num = x / 2;
int tmp = x;
while (num * num >= tmp) {
if (x / 2 == 0) {
break;
}
num = x / 2;
x /= 2;
}
long low = num, high = num * 2, mid = 0;
while (low <= high) {
mid = (low + high) >> 1;
if (mid * mid <= tmp && (mid + 1) * (mid + 1) > tmp) {
break;
} else if (mid * mid > tmp) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return (int) mid;
}
}