给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx

python

# x的算术平方根
class Solution:
    # 二分法
    def sqrtx(self, x: int) -> int:
        if x < 0:
            return -1
        left, right, ans = 0, x, x
        while left <= right:
            mid = left + ((right-left)>>1)
            if mid*mid > x:
                right = mid - 1
            else:
                ans = mid
                left = mid + 1
        return ans
    # 牛顿-拉夫逊迭代
    def sqrtx_newton(self, x: int) -> int:
        if x < 0:
            return -1
        elif x == 0:
            return 0

        C, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + C/x0)
            if abs(x0-xi) < 1e-7:
                break
            x0 = xi
        return int(x0)


if __name__ == "__main__":
    x = 256
    test = Solution()
    print(test.sqrtx(x))
    print(test.sqrtx_newton(x))

golang

package main

import (
	"fmt"
	"math"
)

func main() {
	var x int = 656
	fmt.Println(sqrtx(x))
	fmt.Println(sqrtxNewton(x))
}

func sqrtx(x int) int {
	if x < 0 {
		return -1
	}
	var left int = 0
	var right int = x
	var ans int = -1
	for left <= right {
		var mid int = left + ((right - left) >> 1)
		if mid*mid > x {
			right = mid - 1
		} else {
			ans = mid
			left = mid + 1
		}
	}
	return ans
}

func sqrtxNewton(x int) int {
	if x < 0 {
		return -1
	} else if x == 0 {
		return 0
	}

	C := float64(x)
	x0 := float64(x)
	for {
		xi := 0.5 * (x0 + C/x0)
		if math.Abs(x0 - xi) < 1e-7 {
			break
		}
		x0 = xi
	}
	return int(x0)
}