x 的平方根

实现 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，并且只对正整型有效果。

有疑问加站长微信联系（非本文作者）