题解 | #求平方根#

题解一：二分
题解思路： 二分查找比a<=sqrt(x)<=b
如果 mid*mid <=x 且(mid+1)(mid+1) <x 返回mid
如果mid*mid > x right = mid-1;
否则 left = mid+1;
图示：

复杂度分析：
时间复杂度:O(logn),二分查找的复杂度，每次循环减少一半
空间复杂度;O(1)，只使用了有限常数个变量；
实现如下：

class Solution {
public:
    /**
     *
     * @param x int整型
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        if(x==1) return 1;
        int left = 1,right = x; //左右边界
        while(right>=left){
            int mid = (right+left)/2;  //中间值
            if(mid<=x/mid&&(mid+1)>x/(mid+1)) return mid; // mid*mid可能溢出，所以用除法
            if(mid>x/mid) right = mid -1;
            else  left = mid +1;
        }
        return 0;
    }
};

题解二：利用平方数的性质
题解思路： 利用平方数的性质

复杂度分析：
时间复杂度：O(N)，每次+2的循环，为(1/2)N的时间复杂度,去掉系数，为O(N)
空间复杂度: O(1),只使用了有限常数个变量；
实现如下：

class Solution {
public:
    /**
     *
     * @param x int整型
     * @return int整型
     */
   int sqrt(int x) {
        if(x<=0) return 0;  //小于等于0 返回0
        int ans = 1; 
        int num = 1;
        int  i = 3;
        while(num+i<=x){
            num+=i;  
            ans ++; // 每加一个奇数，ans+1
            i += 2;
        }
        return ans;
    }
};