LeetCode: Sqrt

Title:

Implement int sqrt(int x).

Compute and return the square root of x.

思路：这个平方根肯定是在【1，x】之间，所以在这个区间使用二分查找。需要注意的是，代码中一直使用mid ，x/mid来比较，因为如果使用mid的平法，即使long long都会越界

class Solution {
public:
    int mySqrt(int x) {
        if(x<=1)
        {
            return x;
        }
        
        int left = 1;
        int right = x;
        
        while(left<=right)
        {
            int mid = (left + right)/2;
            if(mid == x/mid)
            {
                return mid;
            }
            else if(mid < x/mid)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        
        return right;
    }
};

 还可以使用牛顿迭代法

http://blog.csdn.net/doc_sgl/article/details/12404971

class Solution {
public:
    int mySqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x ==0)  
            return 0;  
        double pre;  
        double cur = 1;  
        do  
        {  
            pre = cur;  
            cur = x / (2 * pre) + pre / 2.0;  
        } while (abs(cur - pre) > 0.00001);  
        return int(cur);  
    }
};