求平方根

1. 题目描述

实现函数 int sqrt(int x). 计算并返回x的平方根（向下取整）

2. 思路

1. 思路一
   • 遍历[1,x]
   • 当前数<目标值并且下一个数>目标值
2. 思路二
   • 二分

3. 实现

3.1. 遍历

func mySqrt(x int) int {

	for i := 1; i <= x; i++ {
		now := i * i
		next := (i + 1) * (i + 1)

		if now <= x && next > x {
			return i
		}
	}

	return 0
}

3.2. 二分

func mySqrt(x int) int {
    left := 0
    right := x
    for left <= right {
        mid := left + (right-left)>>1
        current := mid * mid
        next := (mid+1) * (mid+1)
        if current <= x && next > x {
            return mid
        }else if current > x {
            right = mid - 1
        }else {
            left = mid + 1
        }
    }
    return 0
}

4. 参考

• 求平方根_牛客题霸_牛客网
• x 的平方根 - x 的平方根 - 力扣（LeetCode）