69. Sqrt(x)

题目

给定一个非负数整数 x。计算并返回该数的算数平方根。向下取整。

解析

首先想到的就是二分法

1. 下界为 0 下，上界为 x
2. 求一个中间数据 m
3. 如果 m*m = x return m
4. 如果 m*m < x 上下界为 [m,x]
5. 如果 m*m > x 上下界为 [0,m]

由于 sqrt 运算不一定能求得标准最小值。所以在上下界判断时，我们可以顺便判断一下区间。

伪代码

二分法

for l<r
if m*m == x
  return m
if m*m > x
  r = m-1
if m*m < x
  if m+1 * m+1 > x
      return m
  l = m+1
return l

代码

func mySqrt(x int) int {
    if x < 2{
        return x
    }
    l := 1
    r := x
    var m int
    for l<r {
        m = (l+r)/2
        if m*m == x {
            return m
        }
        if m*m > x{
            r = m-1
        }else {
            if (m+1)*(m+1) > x {
                return m
            }
            l=m+1
        }
    }
    return l
}