Leetcode 题目069-求平方根

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        int left = 0;
        int right = 65535;
        int mid = 32767;
        //std::cout << INT_MAX<<endl;
        while(left < right){
            if(mid< x/mid ) left = mid!= left ? mid : left+1;
            else if(mid > x/mid) right = mid!= right ? mid : right-1;
            else return mid;
            mid = (left + right) / 2;
        }
        return left-1;        
    }
};

int mySqrt(int x){

    // 牛顿迭代法求Y = X^2 -x 的零点（X是自变量，Y是因变量；x是常量）
    //导数 dY/dX = 2X
    double X0 = 65535.0;
    //double error = X0 * X0 -X
    // int Y0 = X0* X0 - x
    // int x1 = X0 - Y0/2.0 / X0
    while( X0*X0 -x >0.1)
    {
        //x0 = x0 -((x0 * x0) -x)/2.0/x0
        X0 = X0 -(X0/2.0 - x/2.0/X0);
    }

    return X0;
}