69. Sqrt(x)

题目：

解答：

自己设计了两种方案，一种是使用牛顿逼近法，原理是：

​ $a_i + \dfrac{x}{a_i}$ai​+ai​x​ 不断迭代，最终会趋近极限为 $a_i = \sqrt x$ai​=x​

一种是使用二分查找法。下面给出了两种方法的实现，第二种方法给出了递归和迭代两种实现方式。这里magic数等于 $\sqrt{INT\_MAX}$INT_MAX​ 取整。

最后一种，没有递归的调用栈，且都是使用的整数乘法，运行效率最高。

代码：

class Solution {
public:
    // 方法一：使用牛顿逼近法处理，使用的是
    int mySqrt(int x) {
        if( x < 0 )
            return -1;
        else if( x == 0 )   return 0;
        else {
            double a0 = 1.0;
            double a = x;
            while( a - a0 > 0.000001 || a - a0 < -0.000001 )  {
                a0 = a;
                a = (a0 + x / a0) / 2;
            }
            return a;
        }
    }
    // 方法二：二分查找，递归取值
    int calSqrt(int begin, int end, int x){
        int middle = (begin+end) / 2;
        if(middle * middle == x)    return middle;
        if(middle * middle > x)
            return calSqrt(begin, middle, x);
        if((middle+1)*(middle+1) > x)
            return middle;
        return calSqrt(middle, end, x);
    }
    int mySqrt(int x) {
        if(x < 0)   return -1;
        if(x < 2)   return x;
        int magic = 46340;      // sqrt(INT_MAX)
        if(x >= magic * magic)   return magic;
        return calSqrt(1, magic, x);
    }
    // 方法三：迭代二分查找
    int mySqrt(int x) {
        if(x < 0)   return -1;
        if(x < 2)   return x;
        int magic = 46340;      // sqrt(INT_MAX)
        if(x >= magic * magic)   return magic;
        int begin = 1, end = magic;
        while(true){
            int middle = (begin+end) / 2;
            int val = middle * middle;
            if(val == x)    return middle;
            if(val > x){
                end = middle;
                continue;
            }
            if((middle+1)*(middle+1) > x)
                return middle;
            begin = middle;
        }
    }
};

更新会同步在我的网站更新(https://zergzerg.cn/notes/webnotes/leetcode/index.html)