0069.x 的平方根
方法一:二分查找
时间复杂度 $O(\log x)$,空间复杂度 $O(1)$。
func mySqrt(x int) int {
a, b, ans := 0, x, 0
for m := a + (b-a)/2; a <= b; m = a + (b-a)/2 {
if m*m <= x {
ans, a = m, m+1
} else {
b = m - 1
}
}
return ans
}
时间复杂度 $O(\log x)$,空间复杂度 $O(1)$。
func mySqrt(x int) int {
a, b, ans := 0, x, 0
for m := a + (b-a)/2; a <= b; m = a + (b-a)/2 {
if m*m <= x {
ans, a = m, m+1
} else {
b = m - 1
}
}
return ans
}