力扣(LeetCode)之x的平方根

题目：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例：

输入：x = 4
输出：2

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

方法一：暴力搜索法

就是从0开始到x，一个一个去寻找。其具体代码如下：

# 暴力算法
def fun1(x):
    if x == 0 or x == 1:
        return x
    for i in range(x+1):
        if i*i > x:
            return i-1 

方法二：二分法

二分法是暴力算法的改进版本，我们需要左右或者开始(start)和结束(end)两个指针，表示我们要搜索的区间[start, end]。首先我们计算这两个指针的中间值(mid)。如果中间值的平方大于x，就说明x的平方根会比mid小，那么，我们的查找区间就变成了[start, mid]，我们将原来的end = mid，这样我们每一次都能够排除一半的搜索空间，这样的方法就叫做二分法，最后我们能迅速找到最后的答案。

# 二分法
def fun2(x):
    start, end = 0, x 
    index = -1 

    while start <= end:
        mid = int(start + (end - start)/2)
        if mid * mid <= x:
            index = mid
            start = mid + 1 
        else:
            end = mid - 1 
    return index 

方法三：牛顿迭代法

牛顿迭代法使用的是递归函数，假如x=12，我们将12进行因数分解12 = 2 * 6，我们会发现2和6这两个解都不接近x的平方根，但是2和6的平均数较为接近x的平方根，我们只需要不断重复这个操作，我们最终就能够找到x的平方根。下面是具体实现代码：

# 牛顿迭代（递归方法）
def fun3(x, i=1):# 第2个参数可以取值1-x
    if x == 0: return 0
    res = (i + x/i)/2 
    if res == i: return int(i) 
    else: return fun3(x, res)