实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
Golang解决：
package main
import "fmt"
func binaryFind(x, l, r int) (t int) {
m := (l + r + 1) >> 1
if x < m*m {
t = binaryFind(x, l, m-1)
} else if (m+1)*(m+1) < x {
t = binaryFind(x, m, r)
} else {
t = m
if (m+1)*(m+1) == x {
t++
}
}
return
}
func mySqrt(x int) int {
return binaryFind(x, 0, x>>1+1)
}
func main() {
for _, x := range []int{4, 8, 9, 8192, 6, 2147483647} {
fmt.Println(x, mySqrt(x))
}
}
标准输出：
4 2
8 2
9 3
8192 90
6 2
2147483647 46340
这里学到的技巧，对正整型使用移位操作可以完成乘除2的运算，即：
- x = 8; y = x>>1
- x = 8; y = x/2
上下两个运算获得y的值是一致的。
记住，左移一位相当于乘以一个2，右移一位相当于地板除一个2，并且只对正整型有效果。
