LeetCode:开方函数sqrt实现

2019-03-10

要求实现开方函数，面试时这个问题出现的次数还是比较多的。

一：二分查找法

对于一个给定的非负数A，它的平方根都不会大于[A/2+1],故在[0,A/2+1]的范围内进行二分查找

def sqrt(target):
    low = 0
    high = target // 2 + 1
    while low <= high:
        mid = (low + high) // 2
        sq = mid * mid
        if target == sq:
            return mid
        else:
            if target > sq:
                low = mid + 1
            else:
                high = mid - 1

二：牛顿迭代法

二分法，基本都能想到。面试官想要的都是牛顿迭代法的解答。参照百度百科，此时求解方程$f(x)=x^2-a$,开方即求$f(x)=0$,一阶泰勒展开： $$f(x)=f(x_0) + f^{‘}(x_0)(x-x_0)$$ 令为0，可得更新公式： $$x = \frac{1}{2}(x_0+\frac{a}{x_0})$$

def sqrt(target):
    if target == 0:
        return 0
    last = 0
    res =  1
    while(abs(last-res)>=0.000001):
        last = res
        res = 1/2*(res+target/res)
    return res

int sqrt(int x){
    if(x==0 || x==1)
        return x;
    double res=1, last=0;
    while(abs(res - last)>0.00001){
        last=res;
        res = 0.5 * (res + x / res);
    }
    return (int)res;
}

leetcode